теория автоматов / automat-p1

Таблица 5.16

×

××

×

×

b ,× b!

b#, b$

×

×

×

×

×

×

×

×

×

×

×

b , b"

×

×

b ,×

b!

b#, b%

×

×

×

b$, b%

×

×

×

×

×

b , b&

b", b&

×

×

×

×

×

×

b , b"

×

×

×

×

×

×

×

b ×,b

b!,×b

×

×

×

b!,×b

×

×

b$,b

b#,b

b%,b

b ,× b!

×

×

×

×

×

×

×

b#, b$

×

×

b ,×b"

b!,×b"

×

×

×

b!,×b"

×

×

b ×,b"

×

b$,b

b#,b

b%,b

b ,b

×

×

×

b

,b

×

×

×

×

b ,b!

×

×

×

"

!

×

×

×

×

×

b ,b

b", b

×

b , b&

×

×

×

×

×

×

×

×

×

×

b ,b!

b",b#

×

b&,b#

×

×

×

×

b ,b#

×

×

×

×

×

×

b

, b

×

×

×

×

b

,b

×

×

×

b ,b

×

×

"

!

×

×

61

C1 = K3 = {b1},	C7 = K9 = {b11},
C2 = K4 = {b2},	C8 = K10 = {b12},
C3 = K5 = {b6},	C9 = K11 = {b13, b14}.
C4 = K6 = {b1, b10},

Полученное множество финальных классов удовлетворяет условиям полноты и замкнутости, в чем легко убедиться с помощью табл. 5.15. Для этого множества строим нормальную форму автомата, которая и будет минимальным автоматом эквивалентно продолжающим автомат A. Отмеченная таблица переходов минимального автомата приведена в табл. 5.17. По ней на рис. 5.12 построен граф минимального автомата Мура.

Таблица 5.17

w t–

c t–

α

z

z

w

c

c

c

c$

w

c

c

c

c$

β

c

–

c

c!

β

c

–

c

c

β

c!

–

c

c"

w

c"

c#

c'

c5

w

c#

c

–

–

β

c$

–

c"

c%

β

c%

–

c'

c&

w

c&

c'

–

–

w

c'

c

–

–

c 9

z 0

c 4

z1

c 3

β

w0

α

w0

z 0

α

α

z1

z0

c 7

z 1

c 8

c 5

α

0

α

c2

β

w1

w1

c ´´

β

w1

z 1

z1

z 0

z 1

α

z 0

α

c 6

c0´

c 1

β

β

z 1

w 0

z0

62

Ðèñ. 5.12

С помощью табл. 5.3 легко убеждаемся в том, что все допустимые входные слова оператора автомата A и их начальные отрезки принадлежат области определения оператора минимального автомата. По рис. 5.12 находим, что входное слово p = z0z0z1ααα принадлежит области определения оператора минимального автомата. Согласно табл. 5.3, это слово не принадлежит области определения оператора исходного автомата A. Таким образом, минимальный автомат эквивалентно продолжает заданный.

63