4.1. Понятие конечного детерминированного автомата
4.2. Способы задания автоматов
4.3. Эквивалентные состояния. Минимизация к.д.а
4.4. Алгоритм минимизации конечного автомата
4.5. Каноническая таблица. Канонические уравнения
4.6. Функциональные и логические элементы. Проектирование дискретных устройств
4.1. Понятие конечного детерминированного автомата
Автоматы можно рассматривать как механизмы, состоящие из:
- блока управления, который может пребывать в различных состояниях (S внутренний алфавит);
- входного канала;
- выходного канала.
Входной канал считывает входные сигналы (Х) из внешней среды. Выходной канал выдает выходные сигналы (Y) во внешнюю среду. Работа автомата протекает в дискретные такты времени t=1,2,3,…. По команде 
в некотором такте времени 
блок управления установлен в состоянии 
и входной канал воспринимает 
, тогда в этом же такте в выходной канал выдается символ 
, а к следующему такту +1 блок управления перейдет в состояние 
.
Определение. К.Д.А. называется система 
, где 
— алфавит состояний, 
– входной алфавит, 
– выходной алфавит. Множества S, X, Y – конечные.
– функция переходов,
– функция выходов.
Если в автомате выделено одно состояние , называемое начальным (обычно 
), то автомат называется инициальным.
4.2. Способы задания автоматов
-
- Таблица переходов–выходов.
| S\X |
| … |
| … |
|
|
| |||||
| M | |||||
|
|
| ||||
| M | |||||
|
|
