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

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

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

Например, следующей диаграммой Мура (см.

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

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

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

Задача 1.

Выяснить, является ли следующий граф диаграммой Мура некоторого автомата:

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

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

Граф (в) является диаграммой Мура конечного автомата.

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

Задача 2. Построить таблицу автомата, заданного следующей диаграммой Мура (рис. 3.6):

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

Задача 3. Построить диаграмму Мура автомата, заданного таблицей 3.3.

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

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

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

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

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

Значит, из кружочка с номером 2 в кружочек с номером 0 идёт стрелка, помеченная символами 0, 0. Рассматривая ана-логичным образом остальные случаи, получим диаграмму Мура (см. рис. 3.9).

Задачи для самостоятельного решения

1. Автомат задан каноническими уравнениями