Хелпикс

Главная

Контакты

Случайная статья



Если в результате разбиения каждое состояние входит в отдельный блок, это означает, что автомат невозможно минимизировать.



 

Цель минимизации автомата – нахождение минимального эквивалентного автомата для обеспечения наиболее простой реализации. Рассмотрим минимизацию автомата, заданного следующей таблицей переходов.

 

δ (переходы)

λ (выходные сигналы)
Состояние a b a b

Минимизация осуществляется путём последовательного разбиения состояний автомата на блоки.

Начальное разбиение π 0 всегда одинаково и включает все состояния в один блок A0:

π 0 = {A0 = < 1, 2, 3, 4, 5, 6, 7, 8, 9> }

Следующее разбиение π 1 объединяет в один блок те состояния, выходные сигналы которых совпадают при подаче одних и тех же входных сигналов.

 

δ (переходы)

λ (выходные сигналы)
Состояние a b a b

Видим 2 возможные комбинации выходных сигналов – (1, 0) и (0, 1), поэтому разбиваем состояния на 2 блока:

π 1 = {A1 = < 1, 3, 5, 6, 8, 9>; B1 = < 2, 4, 7> }

 

 

Следующее разбиение π 2 проверяет переходы: в какие состояния осуществляется переход и к какому блоку они принадлежат. Например, из состояния 1 происходит переход в состояния 3 и 6 – оба из блока A1, из состояния 2 происходит переход в состояния 4 и 8 – из блоков B1 и A1 соответственно, и т. д. Результаты заносим в таблицу.

 

 

 

π 1
 

δ

λ

δ

  a b a b a b
A1 A1
B1 A1
A1 B1
B1 A1
A1 A1
A1 A1
B1 A1
B1 B1
A1 B1

Получаем 4 возможные комбинации в столбце π 1 – (A1, A1), (В1, A1), (A1, B1) и (B1, B1), поэтому разбиваем состояния на 4 блока:

π 2 = {A2 = < 1, 5, 6>; B2 = < 2, 4, 7>; C2 = < 3, 9>; D2 = < 8> }

 

ВНИМАНИЕ

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

 

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

 

 

 

 

π 1

π 2
 

δ

λ

δ

δ

  a b a b a b a b
A1 A1 C2 A2
B1 A1 B2 D2
A1 B1 A2 B2
B1 A1 B2 C2
A1 A1 C2 A2
A1 A1 C2 A2
B1 A1 B2 C2
B1 B1 B2 B2
A1 B1 A2 B2

Получаем 5 возможных комбинаций и разбиваем состояния на 5 блоков:

π 3 = {A3 = < 1, 5, 6>; B3 = < 2>; C3 = < 4, 7>; D3 = < 3, 9>; E3 = < 8> }

Далее следует следующее разбиение.

 

 

 

π 1

π 2

π 3
 

δ

λ

δ

δ

δ

  a b a b a b a b a b
A1 A1 C2 A2 D3 A3
B1 A1 B2 D2 C3 E3
A1 B1 A2 B2 A3 C3
B1 A1 B2 C2 C3 D3
A1 A1 C2 A2 D3 A3
A1 A1 C2 A2 D3 A3
B1 A1 B2 C2 C3 D3
B1 B1 B2 B2 C3 B3
A1 B1 A2 B2 A3 C3

Получаем 5 возможных комбинаций и разбиваем состояния на 5 блоков:

π 4 = {A4 = < 1, 5, 6>; B4 = < 2>; C4 = < 4, 7>; D4 = < 3, 9>; E4 = < 8> }

Так как π 3 = π 4, то дальнейшее разбиение проводить бессмысленно.

Таким образом, минимизированный автомат вместо 9 изначальных содержит 5 состояний: A, B, C, D и E.

 

ВНИМАНИЕ

Если в результате разбиения каждое состояние входит в отдельный блок, это означает, что автомат невозможно минимизировать.



  

© helpiks.su При использовании или копировании материалов прямая ссылка на сайт обязательна.