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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 58: Строка 58:
 
|statement=
 
|statement=
 
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q</tex> автомата <tex>\mathcal{A}</tex>, принадлежащих множеству <tex>q'</tex>.
 
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q</tex> автомата <tex>\mathcal{A}</tex>, принадлежащих множеству <tex>q'</tex>.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
'''Левое отношение''' регулярного языка <tex>L</tex> для слова <tex>u</tex> из <tex>\Sigma^{*}</tex> {{---}} язык <tex>u^{-1}L = \{ v \in X^{*} \mid uv \in L \}</tex>.
 
}}
 
}}
  
Строка 64: Строка 69:
 
* начальное состояние {{---}} <tex>L</tex>,
 
* начальное состояние {{---}} <tex>L</tex>,
 
* терминальные состояния {{---}} множество отношений, содержащих пустое слово,
 
* терминальные состояния {{---}} множество отношений, содержащих пустое слово,
* функция перехода <tex>\delta(u^{-1} \cdot L, x) = (ux)^{-1} \cdot L</tex>.
+
* функция перехода <tex>\delta(u^{-1}L, x) = (ux)^{-1}L</tex>.
 
Автомат <tex>\mathcal{A}_L</tex> уникален с точностью до изоморфизма и имеет минимальное количество состояний.  
 
Автомат <tex>\mathcal{A}_L</tex> уникален с точностью до изоморфизма и имеет минимальное количество состояний.  
  
Строка 70: Строка 75:
 
|about=5
 
|about=5
 
|statement=
 
|statement=
Автомат минимален тогда и только тогда, когда правые языки его состояний различны.
+
Детерминированный полный достижимый автомат минимален тогда и только тогда, когда правые языки его состояний различны.
 
}}
 
}}
  
Строка 76: Строка 81:
 
===Описание===
 
===Описание===
 
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
 
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
 
 
* Он элегантен и весьма оригинален.
 
* Он элегантен и весьма оригинален.
 
* Он эффективен.
 
* Он эффективен.
 
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
 
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
  
Обладая обычными процедурами обращения <tex>\operatorname{rev}</tex> и детерминизации <tex>\operatorname{det}</tex> конечного [[Детерминированные конечные автоматы|автомата]], мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного [[Детерминированные конечные автоматы|автомата]]. Для этого надо дважды провести его через обе вышеуказанные процедуры:
+
Пусть <tex>\mathcal{A}</tex> {{---}} конечный автомат. <tex>d(\mathcal{A})</tex> {{---}} детерминизированный автомат для <tex>\mathcal{A}</tex>, <tex>r(\mathcal{A})</tex> {{---}} обратный автомат для <tex>\mathcal{A}</tex>.<br>
 +
Обозначим <tex>d(r(\mathcal{A}))</tex> как <tex>dr(\mathcal{A})</tex>, <tex>r(d(r(\mathcal{A})))</tex> как <tex>rdr(\mathcal{A})</tex>, <tex>d(r(d(r(\mathcal{A}))))</tex> как <tex>drdr(\mathcal{A})</tex>.  
  
<tex>mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{r}(FA))))</tex>, где
+
{{Теорема
 
+
|about=Бржозовский, 1962
* <tex>FA</tex> это исходный КА,
+
|statement=
* <tex>\operatorname{rev}</tex> это процедура обращения КА,
+
Пусть <tex>\mathcal{A}</tex> {{---}} автомат (необязательно детерминированный), распознающий язык <tex>L</tex>. Минимальный детерминированный автомат <tex>\mathcal{A}_L</tex> может быть вычислен следующим образом: <tex>\mathcal{A}_L = drdr(\mathcal{A})</tex>.
* <tex>\operatorname{det}</tex> это процедура детерминизации КА,
+
|proof=По построению автомат drdr(A) конечный. Согласно утверждению 2, он распознает язык L.  
* <tex>mFA</tex> это минимизированный КА.
 
 
 
===Корректность===
 
По построению автомат drdr(A) конечный. Согласно утверждению 2, он распознает язык L.  
 
 
Покажем, что правые языки drdr(A) все различны. Из утверждения 1, левые языки dr(A) попарно не пересекаются. Из утверждения 3, правые языки rdr(A) являются левыми языками dr(A). Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык drdr(A) – объединение правых языков rdr(A).  
 
Покажем, что правые языки drdr(A) все различны. Из утверждения 1, левые языки dr(A) попарно не пересекаются. Из утверждения 3, правые языки rdr(A) являются левыми языками dr(A). Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык drdr(A) – объединение правых языков rdr(A).  
 
Поскольку правые языки rdr(A) попарно не пересекаются, все правые языки drdr(A) различны. Тогда, согласно утверждению 5 автомат drdr(A) минимальный.  
 
Поскольку правые языки rdr(A) попарно не пересекаются, все правые языки drdr(A) различны. Тогда, согласно утверждению 5 автомат drdr(A) минимальный.  
 +
}}
  
==Пример работы==
+
===Пример работы===
 
# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>):<br>[[Файл:Fa.png|Исходный НКА]]
 
# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>):<br>[[Файл:Fa.png|Исходный НКА]]
 
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>):<br>[[Файл:Rfa.png|Первый шаг]]
 
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>):<br>[[Файл:Rfa.png|Первый шаг]]

Версия 19:15, 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].


Определение:
Левое отношение регулярного языка [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]

По построению автомат drdr(A) конечный. Согласно утверждению 2, он распознает язык L. Покажем, что правые языки drdr(A) все различны. Из утверждения 1, левые языки dr(A) попарно не пересекаются. Из утверждения 3, правые языки rdr(A) являются левыми языками dr(A). Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык drdr(A) – объединение правых языков rdr(A).

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

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

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

Заключение

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

См. также

Примечания

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