1632
правки
Изменения
м
rollbackEdits.php mass rollback
|statement=
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.
|proof=Рассмотрим состояния <tex>q</tex> и <tex>q'</tex> (<tex>q \neq q'</tex>) в ДКА. Пусть левые языки этих состояний пересекаются, то есть <tex>L_g(q) \cap L_g(q') = \{ w \}</tex>.<br>По окончании процесса допуска слова <tex>w</tex> мы оказываемся в состоянии <tex>q</tex> или <tex>q'</tex>. Следовательно, из какого-то состояния на пути в терминальное существует несколько различных переходов по одному из символов <tex>w</tex>, а значит <tex>\mathcal{A}</tex> {{---}} НКА. Получаем противоречие.
}}
|about=5
|statement=
Детерминированный полный достижимый автомат минимален тогда и только тогда, когда правые языки его состояний различныи все состояния достижимы.|proof=Рассмотрим состояния <tex>q</tex> и <tex>q'</tex> (<tex>q \neq q'</tex>) в ДКА. Пусть их правые языки <tex>L_d(q) = L_d(q')</tex>. Тогда состояния <tex>q</tex> и <tex>q'</tex> можно объединить в одно.<br>Если состояние <tex>q</tex> недостижимо из начального состояния <tex>s</tex>, то его можно удалить из автомата {{---}} это никак не повлияет на язык <tex>L</tex>.
}}
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА]]
