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

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

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

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

Для автомата, приведенного на рис. 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