Алгоритм Бржозовского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Правым языком''' (англ. ''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>.
+
'''Правым языком''' (англ. ''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>.
 
  }}
 
  }}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Левым языком''' (англ. ''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 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>.
 
  }}
 
  }}
  
Строка 62: Строка 62:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Левое отношение''' регулярного языка <tex>L</tex> для слова <tex>u</tex> из <tex>\Sigma^{*}</tex> {{---}} язык <tex>u^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex>.
+
'''Левое отношение''' (англ. ''left quotient'') регулярного языка <tex>L</tex> для слова <tex>u</tex> из <tex>\Sigma^{*}</tex> {{---}} язык <tex>u^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex>.
 
}}
 
}}
  
Строка 92: Строка 92:
 
|statement=
 
|statement=
 
Пусть <tex>\mathcal{A}</tex> {{---}} автомат (необязательно детерминированный), распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A}_L</tex> может быть вычислен следующим образом: <tex>\mathcal{A}_L = drdr(\mathcal{A})</tex>.
 
Пусть <tex>\mathcal{A}</tex> {{---}} автомат (необязательно детерминированный), распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A}_L</tex> может быть вычислен следующим образом: <tex>\mathcal{A}_L = drdr(\mathcal{A})</tex>.
|proof=По построению автомат drdr(A) конечный. Согласно утверждению 2, он распознает язык L.  
+
|proof=
Покажем, что правые языки drdr(A) все различны. Из утверждения 1, левые языки dr(A) попарно не пересекаются. Из утверждения 3, правые языки rdr(A) являются левыми языками dr(A). Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык drdr(A) объединение правых языков rdr(A).  
+
По построению автомат <tex>drdr(\mathcal{A})</tex> детерминированный. Согласно утверждению 2, он распознает язык <tex>L</tex>.<br>
Поскольку правые языки rdr(A) попарно не пересекаются, все правые языки drdr(A) различны. Тогда, согласно утверждению 5 автомат drdr(A) минимальный.  
+
Покажем, что все правые языки <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</tex>):<br>[[Файл:Fa.png|Исходный НКА]]
+
# Исходный [[Недетерминированные конечные автоматы|НКА]] <tex>\mathcal{A}</tex>:<br>[[Файл:Fa.png|Исходный НКА]]
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>):<br>[[Файл:Rfa.png|Первый шаг]]
+
# Первый шаг, <tex>r(\mathcal{A})</tex>:<br>[[Файл:Rfa.png|Первый шаг]]
# Второй шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(FA))</tex>):<br>[[Файл:Drfa.png|Второй шаг]]<br><tex>\operatorname{det}</tex> переименовывает состояния, после этого <tex>0</tex> всегда является начальным состоянием
+
# Второй шаг, <tex>dr(\mathcal{A})</tex>:<br>[[Файл:Drfa.png|Второй шаг]]<br>В детерминизированных автоматах состояния переименованы, так что <tex>0</tex> всегда является начальным состоянием.
# Третий шаг алгоритма (<tex>\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA)))</tex>):<br>[[Файл:Rdrfa.png|Третий шаг]]<br>После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.
+
# Третий шаг, <tex>rdr(\mathcal{A})</tex>:<br>[[Файл:Rdrfa.png|Третий шаг]]<br>После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.
# Заключительный шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))</tex>):<br>[[Файл:Drdrfa.png|Заключительный шаг]]
+
# Заключительный шаг, <tex>drdr(\mathcal{A})</tex>:<br>[[Файл:Drdrfa.png|Заключительный шаг]]
  
 
== Заключение ==
 
== Заключение ==

Версия 19:31, 29 октября 2016

Задача:
Пусть дан автомат [math]\mathcal{A}[/math]. Требуется построить автомат [math]\mathcal{A}_{min}[/math] с наименьшим количеством состояний, распознающий тот же язык, что и [math]\mathcal{A}[/math].


Описание

Пусть [math]q[/math] — состояние автомата [math]\mathcal{A} = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math].

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


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


Утверждение (1):
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.


Определение:
Обратное слово [math]r(u)[/math] для слова [math]u[/math] определяется следующим образом: [math]r(\varepsilon) = \varepsilon[/math] и если [math]u = u_1 u_2 u_3 \dotsc u_p[/math], тогда [math]r(u) = v_1 v_2 v_3 \dotsc v_p[/math], где [math]v_i = u_{p - i + 1}[/math].


Определение:
Обратный язык для языка [math]L[/math] — язык [math]r(L) = \{ u \mid r(u) \in L \}[/math].


Определение:
Обратный автомат для автомата [math]\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle[/math] — автомат [math]r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle[/math], полученный из [math]\mathcal{A}[/math] сменой местами начальных и конечных состояний и сменой направлений переходов.


Утверждение (2):
Если [math]\mathcal{A}[/math] распознает язык [math]L[/math], то [math]r(\mathcal{A})[/math] распознает [math]r(L)[/math].
Утверждение (3):
Если левый язык состояния [math]q[/math] в [math]\mathcal{A}[/math][math]L_g(q)[/math], тогда его левый язык в [math]r(A)[/math][math]L_d(q)[/math]. Аналогично для правого языка [math]q[/math].

Пусть [math]\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle[/math]НКА.
Тогда детерминированный автомат [math]d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle[/math] определяется следующим образом:

  • Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого [math]q' \in Q'[/math] имеем [math]q' \subseteq Q[/math],
  • Начальное состояние в [math]d(\mathcal{A})[/math] — множество из [math]I[/math] начальных состояний автомата [math]\mathcal{A}[/math],
  • Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
  • Пусть [math]q'[/math] — состояние детерминированного автомата и [math]a[/math] – символ из [math]\Sigma[/math]. Если переход из [math]q'[/math] по символу [math]a[/math] определен, тогда, по построению: [math]\delta'(q', a) = \bigcup\limits_{q \in q'}{ \delta(q, a)}[/math].
Утверждение (4):
Правый язык состояния [math]q'[/math] [math]d(\mathcal{A})[/math] эквивалентен объединению правых языков состояний [math]q[/math] автомата [math]\mathcal{A}[/math], принадлежащих множеству [math]q'[/math].


Определение:
Левое отношение (англ. left quotient) регулярного языка [math]L[/math] для слова [math]u[/math] из [math]\Sigma^{*}[/math] — язык [math]u^{-1}L = \{ v \in X^{*} \mid uv \in L \}[/math].


Минимальный автомат [math]\mathcal{A}_{L}[/math] для регулярного языка [math]L[/math] определяется следующим образом:

  • множество состояний — это множество левых отношений языка [math]L[/math],
  • начальное состояние — [math]L[/math],
  • терминальные состояния — множество отношений, содержащих пустое слово,
  • функция перехода [math]\delta(u^{-1}L, x) = (ux)^{-1}L[/math].

Автомат [math]\mathcal{A}_L[/math] уникален с точностью до изоморфизма и имеет минимальное количество состояний.

Утверждение (5):
Детерминированный полный достижимый автомат минимален тогда и только тогда, когда правые языки его состояний различны.

Алгоритм

Описание

Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:

Пусть [math]\mathcal{A}[/math] — конечный автомат. [math]d(\mathcal{A})[/math] — детерминизированный автомат для [math]\mathcal{A}[/math], [math]r(\mathcal{A})[/math] — обратный автомат для [math]\mathcal{A}[/math].
Обозначим [math]d(r(\mathcal{A}))[/math] как [math]dr(\mathcal{A})[/math], [math]r(d(r(\mathcal{A})))[/math] как [math]rdr(\mathcal{A})[/math], [math]d(r(d(r(\mathcal{A}))))[/math] как [math]drdr(\mathcal{A})[/math].

Теорема (Бржозовский, 1962):
Пусть [math]\mathcal{A}[/math] — автомат (необязательно детерминированный), распознающий язык [math]L[/math]. Минимальный детерминированный автомат [math]\mathcal{A}_L[/math] может быть вычислен следующим образом: [math]\mathcal{A}_L = drdr(\mathcal{A})[/math].
Доказательство:
[math]\triangleright[/math]

По построению автомат [math]drdr(\mathcal{A})[/math] детерминированный. Согласно утверждению 2, он распознает язык [math]L[/math].
Покажем, что все правые языки [math]drdr(\mathcal{A})[/math] различны. Из утверждения 1, левые языки [math]dr(\mathcal{A})[/math] попарно не пересекаются. Из утверждения 3, правые языки [math]rdr(\mathcal{A})[/math] являются левыми языками [math]dr(\mathcal{A})[/math]. Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык [math]drdr(\mathcal{A})[/math] — объединение правых языков [math]rdr(\mathcal{A})[/math]. Поскольку правые языки [math]rdr(\mathcal{A})[/math] попарно не пересекаются, все правые языки [math]drdr(\mathcal{A})[/math] различны.

Так как все правые языки [math]drdr(\mathcal{A})[/math] различны, согласно утверждению 5 автомат [math]drdr(\mathcal{A})[/math] минимальный.
[math]\triangleleft[/math]

Пример работы

  1. Исходный НКА [math]\mathcal{A}[/math]:
    Исходный НКА
  2. Первый шаг, [math]r(\mathcal{A})[/math]:
    Первый шаг
  3. Второй шаг, [math]dr(\mathcal{A})[/math]:
    Второй шаг
    В детерминизированных автоматах состояния переименованы, так что [math]0[/math] всегда является начальным состоянием.
  4. Третий шаг, [math]rdr(\mathcal{A})[/math]:
    Третий шаг
    После выполнения этого шага алгоритма оба состояния [math]2[/math] и [math]3[/math] являются начальными.
  5. Заключительный шаг, [math]drdr(\mathcal{A})[/math]:
    Заключительный шаг

Заключение

Самым эффективным алгоритмом минимизации принято считать алгоритм Хопкрофта, который, как и прочие традиционные алгоритмы, работает только с ДКА. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и алгоритм Хопкрофта. В работе[1], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.

См. также

Примечания

Источники информации