Переход от автомата Мили к автомату Мура и наоборот.

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

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

отыскивать классы эквивалентных состояний и заменять их отдельными состояниями.

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

и на одинаковые входные слова выдают одинаковые выходные слова (одинаковой длины).

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

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

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

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

Т.В.
х1 У1 У1 У1 У1 У1 У2
х2 У2 У2 У2 У2 У2 У2

Получен минимальный (с точностью до

изоморфизма) автомат, в котором классы

эквивалентных состояний заменены

именами классов. Он эквивалентен (по

поведению) исходному автомату, но имеет

три состояния вместо шести.

Замечание: Классы, в процессе их

Т.П.
х1 1/А 3/А 6/В 2/А 6/В 4/А
х2 2/А 1/А 3/А 2/А 5/А 5/А

Выделения, могут дробиться, но не

могут объединяться.

Ограниченность метода Гилла.

В полученном автомате наглядно

видно, что автомат не выйдет из

начального состояния А – оно

Т.П.
х1 1/А 3/А 6/В 2/А 6/В 4/А
х2 2/А 1/А 3/А 2/А 5/А 5/А

является тупиковым.

Следовательно, автомат никогда

не перейдет в состояния В и С,

которые в данном случае будут

недостижимыми.

Т.П. А В С
х1 А С А
х2 А В В
Т.П. А В С
х1 А С А
х2 А В В

Анализ тупиковых и недостиж.

состояний может повлиять

на конфигурацию миним.

автомата, либо (что скорее

всего) выявить ошибки в его построении. Однако метод Гилла, как и большинство других методов

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

Особенности минимизации автомата Мура

  У1 У2 У2 У2 У2 У2 У2
 
х1 2/B 3/B 5/B 3/B 4/B 7/B 3/B
х2 1/А 1/А 1/А 1/А 1/А 1/А 1/А
  y1 y2  
  A B  
x1 B B x1

Минимизация автомата Мура отличается первым шагом. Здесь в классы одно-эквивалентных

попадают состояния, отмеченные одинаковыми выходными сигналами.

   
 
 
 

Переход от автомата Мили к автомату Мура и наоборот.

Автоматы Мура и Мили отличаются функцией выходов.

y(t) = j(q(t)) – для автомата Мура

y(t) = j(q(t-1), x(t)) – для автомата Мили

Переход от автомата Мура к автомату Мили заключается в построении таблицы переходов. Построение

состоит в подстановке выходных сигналов, отмечающих состояния в расширенной таблице переходов,

вместо состояний, в которые автомат переходит. Тем самым, если говорить в терминах графов, выходные

сигналы от состояний сдвигаются на стрелки, которые в эти состояния заходят.

А таблица переходов автомата Мили получается из расширенной таблицы переходов автомата Мура

отбрасыванием первой строки.

 
 

  y1 y3 y2
 
 

A B C
x1 A B A
 
 
 
x2

B B C
 
x3

C A C

Т.П. A B C
x1 A B A
x2 B B C
x3 C A C
Т.В. A B C
x1 y1 y3 y1
x2 y3 y3 y2
x3 y2 y1 y2

Наши рекомендации