Алгоритм Бржозовского — различия между версиями
(→Описание) |
м (rollbackEdits.php mass rollback) |
||
(не показана 41 промежуточная версия 8 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
{{Задача | {{Задача | ||
|definition = | |definition = | ||
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>. | Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <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>. | ||
}} | }} | ||
Строка 8: | Строка 88: | ||
===Описание=== | ===Описание=== | ||
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами: | Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами: | ||
− | |||
* Он элегантен и весьма оригинален. | * Он элегантен и весьма оригинален. | ||
* Он эффективен. | * Он эффективен. | ||
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]]. | * Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]]. | ||
− | + | Введём следующие обозначения: | |
+ | *<tex>\mathcal{A}</tex> {{---}} конечный автомат, | ||
+ | *<tex>d(\mathcal{A})</tex> {{---}} детерминизированный автомат для <tex>\mathcal{A}</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>. | ||
− | <tex> | + | {{Теорема |
+ | |about=Бржозовский, 1962 | ||
+ | |statement= | ||
+ | Пусть <tex>\mathcal{A}</tex> {{---}} автомат (необязательно детерминированный), распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A}_L</tex> может быть вычислен следующим образом: <tex>\mathcal{A}_L = drdr(\mathcal{A})</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>\mathcal{A}</tex>:<br>[[Файл:Fa.png|Исходный НКА]] | |
− | + | # Первый шаг, <tex>r(\mathcal{A})</tex>:<br>[[Файл:Rfa.png|Первый шаг]] | |
− | + | # Второй шаг, <tex>dr(\mathcal{A})</tex>:<br>[[Файл:Drfa.png|Второй шаг]]<br>В детерминизированных автоматах состояния переименованы, так что <tex>0</tex> всегда является начальным состоянием. | |
+ | # Третий шаг, <tex>rdr(\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))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В работе<ref>[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A511A421C93DF66BDCC32A0E133D1F99?doi=10.1.1.59.8276&rep=rep1&type=pdf Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions]</ref>, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов. |
− | |||
== См. также == | == См. также == | ||
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | *[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | ||
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] | *[[Минимизация ДКА, алгоритм Хопкрофта (сложность 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 Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Автоматы и регулярные языки]] | [[Категория: Автоматы и регулярные языки]] | ||
+ | [[Категория: Минимизация ДКА]] |
Текущая версия на 19:29, 4 сентября 2022
Задача: |
Пусть дан автомат . Требуется построить автомат с наименьшим количеством состояний, распознающий тот же язык, что и . |
Описание
Пусть
— состояние автомата .Определение: |
Правым языком (англ. right language) называется язык | , распознаваемый автоматом , в котором является уникальным начальным состоянием.
Определение: |
Левым языком (англ. left language) называется язык | , распознаваемый автоматом , в котором является уникальным терминальным состоянием.
Таким образом, допустимые слова языка , проходящие через состояние , фактически разделяются на два языка, а соединение соответствующих слов этих языков по всем состояниям даст исходный язык .
Рассмотрим слово из левого языка . Тогда множество слов — правый контекст слова в языке . Аналогично для правого языка и левого контекста.
Утверждение (1): |
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются. |
Рассмотрим состояния По окончании процесса допуска слова мы оказываемся в состоянии или . Следовательно, из какого-то состояния на пути в терминальное существует несколько различных переходов по одному из символов , а значит — НКА. Получаем противоречие. | и ( ) в ДКА. Пусть левые языки этих состояний пересекаются, то есть .
Определение: |
Обратное слово (англ. reverse of the word) | для слова определяется следующим образом: и если , тогда , где .
Определение: |
Обратный язык (англ. reverse of the language) для языка | — язык .
Определение: |
Обратный автомат (англ. reverse of the automaton) для автомата | — автомат , полученный из сменой местами начальных и конечных состояний и сменой направлений переходов.
Утверждение (2): |
Если распознает язык , то распознает . |
Утверждение (3): |
Если левый язык состояния в — , тогда его левый язык в — . Аналогично для правого языка . |
Пусть НКА.
Тогда детерминированный автомат определяется следующим образом:
- Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого имеем ,
- Начальное состояние в — множество из начальных состояний автомата ,
- Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
- Пусть — состояние детерминированного автомата и – символ из . Если переход из по символу определен, тогда, по построению: .
Утверждение (4): |
Правый язык состояния эквивалентен объединению правых языков состояний автомата , принадлежащих множеству . |
Определение: |
Левое отношение (англ. left quotient) регулярного языка | для слова из — язык .
Минимальный автомат для регулярного языка определяется следующим образом:
- множество состояний — это множество левых отношений языка ,
- начальное состояние — ,
- терминальные состояния — множество отношений, содержащих пустое слово,
- функция перехода .
Автомат
уникален с точностью до изоморфизма и имеет минимальное количество состояний.Утверждение (5): |
Детерминированный автомат минимален тогда и только тогда, когда правые языки его состояний различны и все состояния достижимы. |
Рассмотрим состояния |
Алгоритм
Описание
Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
- Он элегантен и весьма оригинален.
- Он эффективен.
- Он работает даже с недетерминированными конечными автоматами.
Введём следующие обозначения:
- — конечный автомат,
- — детерминизированный автомат для ,
- — обратный автомат для ,
- — результат . Аналогично для и .
Теорема (Бржозовский, 1962): |
Пусть — автомат (необязательно детерминированный), распознающий язык . Минимальный детерминированный автомат может быть вычислен следующим образом: . |
Доказательство: |
По построению автомат |
Пример работы
- Исходный НКА :
- Первый шаг,
- Второй шаг,
В детерминизированных автоматах состояния переименованы, так что всегда является начальным состоянием.
: - Третий шаг,
После выполнения этого шага алгоритма оба состояния и являются начальными.
: - Заключительный шаг,
Заключение
Самым эффективным алгоритмом минимизации принято считать алгоритм Хопкрофта, который, как и прочие традиционные алгоритмы, работает только с ДКА. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и алгоритм Хопкрофта. В работе[1], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.