Доказательство окончено. Покажем, что все состояния автомата Á являются отличимыми

Свойство доказано.

Покажем, что все состояния автомата Á являются отличимыми.

Пусть q ⁱ, q ^j Î Q ^*. Тогда состояния q_{x (i)} и q_{x ( j )} - отличимые. Поскольку = и = , то ¹ . Следовательно, состояния q ⁱ и q ^j также являются отличимыми.

Поскольку " i ( = ) и " i ( = ), то множества функций, вычисляемых автоматами Á и Â, совпадают.

Окончательно получаем, что автоматы Á и Â - эквивалентные, причем автомат Á - минимальный.

Замечание. Использованное в доказательстве теоремы преобразование автомата Â в эквивалентный ему минимальный автомат фактически состоит в том, чтобы заменить всякий класс неотличимых состояний автомата Â на одно состояние.

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

Такая дуга для автомата Á соединяет состояния, соответствующие классам неотличимых состояний начала и конца исходной дуги для Â.

Для автомата, приведенного на рис. 7.6 и имеющего неотличимые состояния q ₀ и q ₁, такое преобразование имеет вид, изображенный на рис. 7.9.

0 (0)

0 (0) 0 (0)

q₁ q₀ q₀

1 (1) 1 (1) 1 (1) 1 (0)

1 (0)

A q₂ B q₁

1 (1) 1 (1)

Рис. 7.9

Дата добавления: 2015-03-31