Изменения

'''Правым языком''' (англ. ''right language'') {{---}} называется язык <tex>L_d(q)</tex>, принимаемый распознаваемый автоматом <tex>\mathcal{A}_{d}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального начального состояния <tex>q</tex>.

'''Левым языком''' (англ. ''left language'') {{---}} называется язык <tex>L_g(q)</tex>, принимаемый распознаваемый автоматом <tex>\mathcal{A}_{g}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального терминального состояния <tex>q</tex>.

'''Левое отношение''' (англ. ''left quotient'') регулярного языка <tex>L</tex> для слова <tex>u</tex> из <tex>\Sigma^{*}</tex> {{---}} язык <tex>u^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex>.

|proof=По построению автомат <tex>drdr(\mathcal{A}) конечный</tex> детерминированный. Согласно утверждению 2, он распознает язык <tex>L</tex>. <br> Покажем, что все правые языки <tex>drdr(\mathcal{A}) все </tex> различны. Из утверждения 1, левые языки <tex>dr(\mathcal{A}) </tex> попарно не пересекаются. Из утверждения 3, правые языки <tex>rdr(\mathcal{A}) </tex> являются левыми языками <tex>dr(\mathcal{A})</tex>. Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык <tex>drdr(\mathcal{A}) – </tex> {{---}} объединение правых языков <tex>rdr(\mathcal{A})</tex>. Поскольку правые языки <tex>rdr(\mathcal{A}) </tex> попарно не пересекаются, все правые языки <tex>drdr(\mathcal{A}) </tex> различны. ТогдаТак как все правые языки <tex>drdr(\mathcal{A})</tex> различны, согласно утверждению 5 автомат <tex>drdr(\mathcal{A}) </tex> минимальный.

# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA\mathcal{A}</tex>):<br>[[Файл:Fa.png|Исходный НКА]]# Первый шаг алгоритма (, <tex>r(\operatornamemathcal{revA}(FA)</tex>):<br>[[Файл:Rfa.png|Первый шаг]]# Второй шаг алгоритма (, <tex>\operatorname{det}dr(\operatornamemathcal{revA}(FA))</tex>):<br>[[Файл:Drfa.png|Второй шаг]]<br><tex>\operatorname{det}</tex> переименовывает В детерминизированных автоматах состоянияпереименованы, после этого так что <tex>0</tex> всегда является начальным состоянием.# Третий шаг алгоритма (, <tex>\operatorname{rev}(\operatorname{det}rdr(\operatornamemathcal{revA}(FA)))</tex>):<br>[[Файл:Rdrfa.png|Третий шаг]]<br>После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.# Заключительный шаг алгоритма (, <tex>\operatorname{det}(\operatorname{rev}(\operatorname{det}drdr(\operatornamemathcal{revA}(FA))))</tex>):<br>[[Файл:Drdrfa.png|Заключительный шаг]]