Представление автомата

Для описания работы автомата чаще всего используют таблицы и графы переходов. В табл. 4.1 приведен пример представления автомата Мили, а в табл. 4.2 - автомата Мура.

Таблица 4.1

		...
		...
...	...	...	...
		...

Таблица 4.2

		...
		...
...	...	...	...
		...

Автомат называется полностью определённым, если множество пар для функций перехода и выхода равны множеству пар . У частично определённого автомата функции d и l определены на множестве не всех пар ; в этом случае некоторые клетки не заполнены.

Граф переходов строится следующим образом. Две вершины и (исходное состояние и состояние перехода) соединяются дугой, направленной от к , если в автомате имеется переход из в (если ). Для автомата Мили дуге () приписывается входной символ и выходной . Для автомата Мура входной символ записывается внутри вершины или рядом с ней, а дуге приписывается только входной символ .

Пример 4.1. Автомат Мили A₁ задан таблично (табл. 4.3) и графически (рис. 4.1).

S1 S2 S3

Таблица 4.3

РРис. 4.1. Граф автомата А₁

Пример 4.2. Автомат Мура A₂ задан таблично (табл. 4.4) и графически (рис. 4.2).

Таблица 4.4

Рис. 4.2. Граф автомата А₂