Изменения

'''Правым языком''' (англ. ''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>является уникальным терминальным состоянием.

'''Обратное слово''' (англ. ''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>.

'''Обратный язык''' (англ. ''reverse of the language'') для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.

'''Обратный автомат''' (англ. ''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> сменой местами начальных и конечных состояний и сменой направлений переходов.

* функция перехода <tex>\delta(u^{-1} \cdot L, x) = (ux)^{-1} \cdot L</tex>.

Автомат Детерминированный автомат минимален тогда и только тогда, когда правые языки его состояний различныи все состояния достижимы.|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>.

Обладая обычными процедурами обращения Введём следующие обозначения:*<tex>\mathcal{A}</tex> {{---}} конечный автомат,*<tex>d(\operatornamemathcal{revA})</tex> и детерминизации {{---}} детерминизированный автомат для <tex>\operatornamemathcal{detA}</tex> конечного [[Детерминированные конечные автоматы|автомата]], мы*<tex>r(\mathcal{A})</tex> {{---}} обратный автомат для <tex>\mathcal{A}</tex>, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного [[Детерминированные конечные автоматы|автомата]]*<tex>dr(\mathcal{A})</tex> {{---}} результат <tex>d(r(\mathcal{A}))</tex>. Аналогично для <tex>rdr(\mathcal{A})</tex> и <tex>drdr(\mathcal{A})</tex>. Для этого надо дважды провести его через обе вышеуказанные процедуры:

{{Теорема|about=Бржозовский, 1962|statement=Пусть <tex>mFA = \operatorname mathcal{detA}(\operatorname</tex> {rev}(\operatorname{det---}(\operatorname{r}автомат (FA)необязательно детерминированный)))</tex>, где * распознающий язык <tex>FAL</tex> это исходный КА,* . Минимальный детерминированный автомат <tex>\operatornamemathcal{revA}_L</tex> это процедура обращения КА,* может быть вычислен следующим образом: <tex>\operatornamemathcal{A}_L = drdr(\mathcal{detA})</tex> это процедура детерминизации КА,* <tex>mFA</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}rdr(\operatornamemathcal{detA}(\operatorname{rev}(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|Заключительный шаг]]

* [https://pdfs.semanticscholar.org/f3be/b5e5825e6eedaab7f382341c9dd9c2ab33fa.pdf J.-M. Champarnaud, A. Khorsi, T. Paranthoen {{---}} Split and join for minimizing: Brzozowski's algorithm]* [http://sovietov.com/txt/minfa/minfa.html Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата]