188
правок
Изменения
→Источники информации
{{Задача
|definition =
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
}}
==Описание==
Пусть <tex>q</tex> {{---}} состояние автомата <tex>\mathcal{A} = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>.
{{Определение
|definition=
'''Правым языком''' (англ. ''right language'') называется язык <tex>L_d(q)</tex>, распознаваемый автоматом <tex>\mathcal{A}</tex>, в котором <tex>q</tex> является уникальным начальным состоянием.
}}
{{Определение
|definition=
'''Левым языком''' (англ. ''left language'') называется язык <tex>L_g(q)</tex>, распознаваемый автоматом <tex>\mathcal{A}</tex>, в котором <tex>q</tex> является уникальным терминальным состоянием.
}}
Таким образом, допустимые слова языка <tex>L</tex>, проходящие через состояние <tex>q</tex>, фактически разделяются на два языка, а соединение соответствующих слов этих языков по всем состояниям даст исходный язык <tex>L</tex>.<br>
Рассмотрим слово <tex>y</tex> из левого языка <tex>L_g(q)</tex>. Тогда множество слов <tex>L_d(q)</tex> {{---}} [[Контексты_и_синтаксические_моноиды|правый контекст]] слова <tex>y</tex> в языке <tex>L</tex>. Аналогично для правого языка и левого контекста.
{{Утверждение
|about=1
|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=2
|statement=
Если <tex>\mathcal{A}</tex> распознает язык <tex>L</tex>, то <tex>r(\mathcal{A})</tex> распознает <tex>r(L)</tex>.
}}
{{Утверждение
|about=3
|statement=
Если левый язык состояния <tex>q</tex> в <tex>\mathcal{A}</tex> {{---}} <tex>L_g(q)</tex>, тогда его левый язык в <tex>r(A)</tex> {{---}} <tex>L_d(q)</tex>. Аналогично для правого языка <tex>q</tex>.
}}
Пусть <tex>\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle</tex> {{---}} [[Недетерминированные_конечные_автоматы|НКА]].<br>Тогда детерминированный автомат <tex>d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle</tex> определяется следующим образом:
* Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого <tex>q' \in Q'</tex> имеем <tex>q' \subseteq Q</tex>,
* Начальное состояние в <tex>d(\mathcal{A})</tex> {{---}} множество из <tex>I</tex> начальных состояний автомата <tex>\mathcal{A}</tex>,
* Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
* Пусть <tex>q'</tex> {{---}} состояние детерминированного автомата и <tex>a</tex> – символ из <tex>\Sigma</tex>. Если переход из <tex>q'</tex> по символу <tex>a</tex> определен, тогда, по построению: <tex>\delta'(q', a) = \bigcup\limits_{q \in q'}{ \delta(q, a)}</tex>.
{{Утверждение
|about=4
|statement=
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q</tex> автомата <tex>\mathcal{A}</tex>, принадлежащих множеству <tex>q'</tex>.
}}
{{Определение
|definition=
'''Левое отношение''' (англ. ''left quotient'') регулярного языка <tex>L</tex> для слова <tex>u</tex> из <tex>\Sigma^{*}</tex> {{---}} язык <tex>u^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex>.
}}
Минимальный автомат <tex>\mathcal{A}_{L}</tex> для регулярного языка <tex>L</tex> определяется следующим образом:
* множество состояний {{---}} это множество левых отношений языка <tex>L</tex>,
* начальное состояние {{---}} <tex>L</tex>,
* терминальные состояния {{---}} множество отношений, содержащих пустое слово,
* функция перехода <tex>\delta(u^{-1}L, x) = (ux)^{-1}L</tex>.
Автомат <tex>\mathcal{A}_L</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>.
}}
===Описание===
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
* Он элегантен и весьма оригинален.
* Он эффективен.
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
{{Теорема|about=Бржозовский, 1962|statement=Пусть <tex>\mathcal{A}</tex> {{---}} автомат (необязательно детерминированный), распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A}_L</tex>mFA может быть вычислен следующим образом: <tex>\mathcal{A}_L = det(revdrdr(det(rev(FA)))\mathcal{A})</tex>, где.|proof=* По построению автомат <tex>FAdrdr(\mathcal{A})</tex> это исходный КАдетерминированный. Согласно утверждению 2,он распознает язык <tex>L</tex>.<br> * Покажем, что все правые языки <tex>revdrdr(\mathcal{A})</tex> это процедура обращения КАразличны. Из утверждения 1,* левые языки <tex>detdr(\mathcal{A})</tex> это процедура детерминизации КАпопарно не пересекаются. Из утверждения 3,* правые языки <tex>rdr(\mathcal{A})</tex> являются левыми языками <tex>mFAdr(\mathcal{A})</tex> это минимизированный КА. ===Корректность=====Пример работы==* Исходный [[Недетерминированные конечные автоматы|НКА]] Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык <tex>drdr(\mathcal{A})</tex> {{---}} объединение правых языков <tex>FArdr(\mathcal{A})</tex>):[[Файл:Fa.png|Исходный НКА]]* Первый шаг алгоритма Поскольку правые языки <tex>rdr(\mathcal{A})</tex> попарно не пересекаются, все правые языки <tex>revdrdr(FA\mathcal{A})</tex>):[[Файл:Rfaразличны.png|Первый шаг]]* Второй шаг алгоритма Так как все правые языки <tex>drdr(\mathcal{A})</tex>detразличны, согласно утверждению 5 автомат <tex>drdr(rev(FA)\mathcal{A})</tex>):минимальный. [[Файл:Drfa.png|Второй шаг]]}}
===Пример работы===# Исходный [[Недетерминированные конечные автоматы|НКА]] <tex>\mathcal{A}</tex>:<br>[[Файл:Fa.png|Исходный НКА]]# Первый шаг, <tex>r(\mathcal{A})</tex>det:<br>[[Файл:Rfa.png|Первый шаг]]# Второй шаг, <tex>dr(\mathcal{A})</tex> переименовывает :<br>[[Файл:Drfa.png|Второй шаг]]<br>В детерминизированных автоматах состоянияпереименованы, после этого так что <tex>0</tex> всегда является начальным состоянием.* # Третий шаг алгоритма (, <tex>revrdr(det(rev(FA))\mathcal{A})</tex>):<br>[[Файл:Rdrfa.png|Третий шаг]]<br>После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.# Заключительный шаг, <tex>drdr(\mathcal{A})</tex>:<br>[[Файл:Drdrfa.png|Заключительный шаг]]
== См. также ==
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
==ЛитератураПримечания==<references/>==Источники информации==* [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 Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА]]
