4. Конечные автоматы
Цель данного занятия - освоить язык описания конечных автоматов и приобрести навыки в их анализе и взаимном преобразовании.
4.1. Общие положения
Конечный
автомат - это набор из пяти элементов
,
где
алфавит внутренних состояний;
входной
алфавит (алфавит входных символов);
выходной
алфавит (алфавит выходных символов);
функция переходов из состояния в состояние;
функция выходов.
В
теории автоматов наиболее часто
рассматриваются автоматы Мили и Мура,
у которых функции переходов имеют
одинаковый вид (
),
а функции выходов существенно различны
(
для автомата Мили и
для автомата Мура), что определяет разное
поведение автоматов. При этом решают
задачи анализа и синтеза автоматов, их
взаимных преобразований, установление
эквива-лентности автоматов и др.
4.2. Представление автомата
Для описания работы автомата чаще всего используют таблицы и графы переходов. В табл. 4.1 приведен пример представления автомата Мили, а в табл. 4.2 автомата Мура.
Таблица 4.1
-
...
...
...
...
...
...
...
Таблица 4.2
-
...
...
...
...
...
...
...
Автомат
называется полностью
определённым,
если множество пар для функций перехода
и выхода равны множеству пар
.
У частично
определённого автомата функции
и
определены на множестве не всех пар
;
в этом случае некоторые клетки не
заполнены.
Граф
переходов строится следующим образом.
Две вершины
и
(исходное состояние и состояние перехода)
соединяются дугой, направленной от
к
,
если в автомате имеется переход из
в
(если
).
Для автомата Мили дуге (
)
приписывается входной символ
и выходной
.
Для автомата Мура входной символ
записывается внутри вершины
или рядом с ней, а дуге приписывается
только входной символ
.
Пример
4.1.
Автомат Мили
задан таблично (табл. 4.3)
и графически (рис. 4.1).
РРис. 4.1. Граф автомата А1
Пример
4.2.
Автомат Мура
задан таблично (табл. 4.4)
и графически (рис. 4.2).
Рис. 4.2. Граф автомата А2