4.1.2. Диаграмма Мура и таблица автоматов

Наряду с каноническими уравнениями работа автомата может быть описана с помощью диаграммы Мура или таблицы.

Диаграммой Мура автомата называется ориентированный граф, вершинами которого являются состояния и для каждого равенства вида граф имеет ребро, идущее из в на котором стоит метка где

Например, диаграммой Мура, изображённой на рисунке 4.4,

изображается автомат, у которого . . . . . .

Таблицей автомата называется прямоугольная таблица с строками и столбцами, причём в клетке, стоящей на пересечении -й строчки и -го столбца написаны символы и

Например, автомат из предыдущего примера может быть задан таблицей

	0	1
	a	b
	a	c
	b	c

Разберём несколько типовых задач.

Упражнение 1. Выяснить, являются ли графы, изображённые на рисунке 4.5, диаграммами Мура некоторого автомата:

Решение. Граф (а) не является диаграммой Мура никакого автомата, так как на диаграмме не указано, в какое состояние должен переходить автомат, если он находится в состоянии и получает на входе символ 1. Граф (б) также не является диаграммой Мура, так как переход из состояния при получении символа определён неоднозначно. Граф (в) является диаграммой Мура конечного автомата.

Из определения конечного автомата и диаграммы Мура следует, что ориентированный граф, рёбра которого помечены символами ( является диаграммой Мура некоторого конечного автомата в том и только том случае, если из каждого состояния выходило по одной стрелке для каждого символа

Упражнение 2. Построить таблицу автомата, заданного диаграммой Мура, изображённого на рисунке 4.6.

Решение. Так как и то в клетке надо записать символы и 0. Аналогично заполняются другие клетки таблицы, и мы получаем:

	a	b
	0	0
	1	0
	1	0
	1	1

Упражнение 3. Автомат задан таблицей

	0	1	2
	2	1	2
	0	0	1
	1	2	0

Построить диаграмму Мура этого автомата.

Решение. Первая клетка показывает, что автомат, находясь в состоянии и приняв символ 0, должен перейти в состояние и выдать на выход символ 2. Следовательно, из в должно идти ребро, помеченное символами 0 и 2 (см. рис. 4.7).

Рассуждая аналогично для других клеток, мы получаем диаграмму Мура данного автомата (см. рис. 4.8).

Упражнение 4. Автомат, у которого задан каноническими уравнениями

Построить диаграмму Мура этого автомата.

Решение. Пусть Тогда и Следовательно, на диаграмме Мура из кружочка, обозначающего состояние 0, в этот же кружочек должна идти стрелка, помеченная символами 0, 0. Пусть теперь, скажем, Тогда и Значит, из кружочка с номером 2 в кружочек с номером 0 идёт стрелка, помеченная символами 0, 0. Рассматривая аналогичным образом остальные случаи, получим диаграмму Мура (см. рис. 4.9).