1632
правки
Изменения
м
{{В разработке}}
* Он элегантен и весьма оригинален.{{Утверждение* Он эффективен.|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>rev\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>detI</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>.
* {{Определение|definition='''Левое отношение''' (англ. ''left quotient'') регулярного языка <tex>FAL</tex> это исходный КА,* для слова <tex>revu</tex> это процедура обращения КА,* из <tex>det\Sigma^{*}</tex> это процедура детерминизации КА,* {{---}} язык <tex>mFAu^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex> это минимизированный КА.}}
def fa_rev(fa):==Алгоритм== rfa = ==Описание===Алгоритм минимизации конечных [list(fa[QДетерминированные конечные автоматы|автоматов]]), listБржозовского (fa[Janusz A]), [], list(fa[F]), list(fa[S])] rfa[T] = [[[] for i in range(0, len. (fa[A]John)Brzozowski)] for j in range(0выделяется, len(fa[Q]))] for t1 in range(0по крайней мере, len(fa[Q]))следующими качествами: for a in range(0, len(fa[A])):* Он элегантен и весьма оригинален. for t2 in fa[T][t1][a]:* Он эффективен. rfa* Он работает даже с [T][t2Недетерминированные конечные автоматы|недетерминированными конечными автоматами][a].append(t1) return rfa
# Детерминизация КАВведём следующие обозначения:*<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>.
def fa_det(fa):{{Теорема def reachable(q|about=Бржозовский, l):1962 t |statement= [] for a in rangeПусть <tex>\mathcal{A}</tex> {{---}} автомат (0необязательно детерминированный), len(fa[распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A]))}_L</tex> может быть вычислен следующим образом: ts <tex>\mathcal{A}_L = setdrdr(\mathcal{A})</tex>. for i in q[l]: # объединение множеств (достижимых из l) состояний для символа a ts |proof= setПо построению автомат <tex>drdr(fa[T][i][a]\mathcal{A}) if not ts: t</tex> детерминированный.append([]) continue try: i = qСогласно утверждению 2, он распознает язык <tex>L</tex>.index(ts)<br> except ValueError: i = lenПокажем, что все правые языки <tex>drdr(q\mathcal{A}) q</tex> различны.appendИз утверждения 1, левые языки <tex>dr(ts\mathcal{A}) t</tex> попарно не пересекаются.appendИз утверждения 3, правые языки <tex>rdr([i]\mathcal{A}) return t dfa = [[], list</tex> являются левыми языками <tex>dr(fa[\mathcal{A]})</tex>. Таким образом, []они попарно не пересекаются. Согласно утверждению 4, [0], []] q = [setправый язык <tex>drdr(fa[S]\mathcal{A})] while len</tex> {{---}} объединение правых языков <tex>rdr(dfa[T]\mathcal{A}) < len/tex>. Поскольку правые языки <tex>rdr(q\mathcal{A}): dfa[T].append(reachable(q</tex> попарно не пересекаются, lenвсе правые языки <tex>drdr(dfa[T]))\mathcal{A})</tex> различны. dfa[Q] = rangeТак как все правые языки <tex>drdr(0\mathcal{A})</tex> различны, lenсогласно утверждению 5 автомат <tex>drdr(q\mathcal{A})) dfa[F] = [q</tex> минимальный.index(i) for i in q if set(fa[F]) & i] return dfa}}
def fa_min(fa):== Заключение == return fa_detСамым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (fa_revсложность O(fa_detn log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (fa_revсложность O(fan 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))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.
rollbackEdits.php mass rollback
{{Задача
|definition =
}}
==АлгоритмОписание==Пусть <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> (Janusz A<tex>q \neq q'</tex>) в ДКА. Пусть левые языки этих состояний пересекаются, то есть <tex>L_g(Johnq) Brzozowski\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=4|statement=Правый язык состояния <tex>q'</tex>mFA = det<tex>d(rev(det(rev(FA)))\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q</tex> автомата <tex>\mathcal{A}</tex>, гдепринадлежащих множеству <tex>q'</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>.# Обращение КА}}
===Пример работы===# Алгоритм БржозовскогоИсходный [[Недетерминированные конечные автоматы|НКА]] <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))]]
==ЛитератураПримечания==<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 Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА]]
