ВУЗ:
Рубрика:
x
1
1
a
2
a
3
a
4
a
1
a
2
a
1
a
x
2
5
a
5
a
5
a
2
a
7
b
2
a
2
a
Таблица 26
В результате выполнения всех возможных разбиений (табл.27, 28, 29)
получим минимальный автомат Мура (табл.30).
Таблица 27 Таблица 28
Таблица 29 Таблица 30
Обратим внимание на то важное обстоятельство, что используемая про-
цедура минимизации в ряде случаев может быть ”излишне” универсальной. Она
не учитывает того, что мы рассматриваем лишь инициальные автоматы.
(Начальное состояние во всех примерах, независимо от использования
различных систем обозначения, в таблицах всегда идет первым). А например,
для инициального автомата с
начальным состоянием а (см. табл. 30)
невозможен переход в состояние с, т.е. состояние с является недостижимым.
Следовательно, его можно исключить. Из исходного автомата можно убрать
недостижимые состояния до начала процесса минимизации. (Существуют и
другие ”аномальные” ситуации. Какие, на ваш взгляд?).
1 2 3 4 5 6 7
х
1
1
a
2
a
3
a
4
a
2
a
1
a
1
a
х
2
5
b
5
b
5
b
2
a
2
a
7
c
2
a
1 2 3 4 5 6 7
х
1
1
a
2
a
3
a
4
b
2
a
1
a
1
a
х
2
5
c
5
c
5
c
2
a
2
a
7
d
2
a
1 2 3 4 5 6 7
х
1
1
a
2
a
3
a
4
b
2
a
1
a
1
a
х
2
5
d
5
d
5
d
2
a
2
a
7
e
2
a
y
1
y
1
y
1
y
1
y
2
a b c d e
x
1
a b a a a
x
2
d a a e a
a b a c
a b c a b c d
a b c d a b c d e
a b c d e
a b c d e
1 2 3 4 1 2 1
x1
a a a a a a a
5 5 5 2 7 2 2
x2
a a a a b a a
a b a c
Таблица 26
В результате выполнения всех возможных разбиений (табл.27, 28, 29)
получим минимальный автомат Мура (табл.30).
a b c a b c d
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 2 1 1 1 2 3 4 2 1 1
х1 х1
a a a a a a a a a a b a a a
5 5 5 2 2 7 2 5 5 5 2 2 7 2
х2 х2
b b b a a c a c c c a a d a
a b c d a b c d e
Таблица 27 Таблица 28
a b c d e
y1 y1 y1 y1 y2
1 2 3 4 5 6 7
a b c d e
1 2 3 4 2 1 1
х1
a a a b a a a x1 a b a a a
5 5 5 2 2 7 2
х2 x2 d a a e a
d d d a a e a
a b c d e
Таблица 29 Таблица 30
Обратим внимание на то важное обстоятельство, что используемая про-
цедура минимизации в ряде случаев может быть ”излишне” универсальной. Она
не учитывает того, что мы рассматриваем лишь инициальные автоматы.
(Начальное состояние во всех примерах, независимо от использования
различных систем обозначения, в таблицах всегда идет первым). А например,
для инициального автомата с начальным состоянием а (см. табл. 30)
невозможен переход в состояние с, т.е. состояние с является недостижимым.
Следовательно, его можно исключить. Из исходного автомата можно убрать
недостижимые состояния до начала процесса минимизации. (Существуют и
другие ”аномальные” ситуации. Какие, на ваш взгляд?).
