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

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

 

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

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

 

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

0(0)

0(0)0(0)

q1 q0 q0

 

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

1(0)

A q2 B q1

1(1)1(1)

Рис. 7.9








Дата добавления: 2015-09-18; просмотров: 551;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.