188
правок
Изменения
→Источники информации
|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> {{---}} НКА. Получаем противоречие.
}}
{{Определение
|definition=
'''Обратное слово''' (англ. ''reverse of the word'') <tex>r(u)</tex> для слова <tex>u</tex> определяется следующим образом: <tex>r(\varepsilon) = \varepsilon</tex> и если <tex>u = u_1 u_2 u_3 \dotsc u_p</tex>, тогда <tex>r(u) = v_1 v_2 v_3 \dotsc v_p</tex>, где <tex>v_i = u_{p - i + 1}</tex>.
}}
{{Определение
|definition=
'''Обратный язык''' (англ. ''reverse of the language'') для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
}}
{{Определение
|definition=
'''Обратный автомат''' (англ. ''reverse of the automaton'') для автомата <tex>\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle</tex> {{---}} автомат <tex>r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle</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>.
}}
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА]]
