Минимизация автоматов

Выходов

Переходов

и

Пример 2 (автомат Мура).

Построить автомат, на вход которого могут поступать монеты 1, 2, 3 коп. Автомат выдает сигнал “чет”, если поступившая сумма в данный момент четная и “нечет”, если наоборот.

чет нечет

Это автомат Мура. Поэтому выходные сигналы приписаны не стрелкам, а к состояниям, которыми они однозначно определяются. Табличное представление сводится к одной таблице – расширенной таблице переходов. В ней добавляется верхняя строка, позволяющая приписать выходные сигналы состояниям.

Автоматы различной конфигурации могут реализовывать одну и ту же функцию. Для практических целей важно уметь находить автомат с минимальным количеством состояний, реализующий заданное поведение. Число состояний абстрактного автомата определяет при практической реализации число необходимых элементов памяти.

Кстати, первый рассмотренный автомат был (сознательно) построен избыточным. От состояния q₃ очень просто избавиться, передав его функции состоянию q₀.

Существуют различные методы минимизации. К числу простейших относитсяМетод Гилла, позволяющий отыскивать классы эквивалентных состояний и заменять их отдельными состояниями.

Два автомата называются эквивалентными, если они имеют одинаковые входные и выходные алфавиты, и на одинаковые входные слова выдают одинаковые выходные слова (одинаковой длины).

Два состояния называются 1-эквивалентными, если они не различимы с помощью одного входного сигнала (символа).

Состояния называются k-эквивалентными, если начиная с них неразличимы входные слова длиной в k.

Если состояния k-эквивалентные для любого k, то они называются эквивалентными.

Рассмотрим минимизацию методом Гилла на каком-то конкретном автомате Мили.

A B

- I - эквивалентные

Т.П.
x1	1/A	3/A	6/B	2/A	6/B	4/A
x2	2/A	1/A	3/A	2/A	5/A	5/A

- II - эквивалентные

A B A B C

A B C

Т.П.
x1	1/A	3/A	6/B	2/C	6/C	4/A
x2	2/A	1/A	3/A	2/B	5/B	5/B

- III - эквивалентные

A B C

Получен минимальный (с точностью до изоморфизма) автомат, в котором классы эквивалентных состояний заменены именами классов. Он эквивалентен (по поведению) исходному автомату, но имеет три состояния вместо шести.

Замечание. Классы, в процессе их выделения, могут дробиться, но не могут объединяться.

Ограниченность метода Гилла. В полученном автомате наглядно видно, что автомат не выйдет из начального состояния А – оно является тупиковым.Следовательно, автомат никогда не перейдет в состояния В и С, которые в данном случае будут недостижимыми.

Анализ тупиковых и недостижимых состояний может повлиять на конфигурацию минимального автомата, либо (что скорее всего) выявить ошибки в его построении.

Однако метод Гилла, как и большинство других методов минимизации, не учитывает влияния тупиковых и недостижимых состояний на результирующий автомат.