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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
 
(не показано 12 промежуточных версий 2 участников)
Строка 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}</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}</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>. Аналогично для правого языка и левого контекста.
  
 
{{Утверждение
 
{{Утверждение
Строка 19: Строка 22:
 
|statement=
 
|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=
 
|definition=
'''Обратное слово''' <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>.
+
'''Обратное слово''' (англ. ''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=
 
|definition=
'''Обратный язык''' для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
+
'''Обратный язык''' (англ. ''reverse of the language'') для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Обратный автомат''' для автомата <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> сменой местами начальных и конечных состояний и сменой направлений переходов.
+
'''Обратный автомат''' (англ. ''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> сменой местами начальных и конечных состояний и сменой направлений переходов.
 
}}
 
}}
  
Строка 57: Строка 61:
 
|about=4
 
|about=4
 
|statement=
 
|statement=
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q \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=
 +
'''Левое отношение'''  (англ. ''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) выделяется, по крайней мере, следующими качествами:
 
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (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>,
 +
*<tex>dr(\mathcal{A})</tex> {{---}} результат <tex>d(r(\mathcal{A}))</tex>. Аналогично для <tex>rdr(\mathcal{A})</tex> и <tex>drdr(\mathcal{A})</tex>.
  
<tex>mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(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=
* <tex>mFA</tex> это минимизированный КА.
+
По построению автомат <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> различны.  
Корректность алгоритма доказана в работе<ref>[http://www.researchgate.net/publication/255626373_Split_and_join_for_minimizing__Brzozowski's_algorithm Split and join for minimizing : Brzozowski's algorithm]</ref>
+
Так как все правые языки <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|Заключительный шаг]]
  
 
== Заключение ==
 
== Заключение ==
Строка 99: Строка 126:
 
<references/>
 
<references/>
 
==Источники информации==
 
==Источники информации==
* [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
+
* [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 Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Минимизация ДКА]]

Текущая версия на 16:35, 13 ноября 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}[/math], в котором [math]q[/math] является уникальным начальным состоянием.


Определение:
Левым языком (англ. left language) называется язык [math]L_g(q)[/math], распознаваемый автоматом [math]\mathcal{A}[/math], в котором [math]q[/math] является уникальным терминальным состоянием.


Таким образом, допустимые слова языка [math]L[/math], проходящие через состояние [math]q[/math], фактически разделяются на два языка, а соединение соответствующих слов этих языков по всем состояниям даст исходный язык [math]L[/math].
Рассмотрим слово [math]y[/math] из левого языка [math]L_g(q)[/math]. Тогда множество слов [math]L_d(q)[/math]правый контекст слова [math]y[/math] в языке [math]L[/math]. Аналогично для правого языка и левого контекста.

Утверждение (1):
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.
[math]\triangleright[/math]
Рассмотрим состояния [math]q[/math] и [math]q'[/math] ([math]q \neq q'[/math]) в ДКА. Пусть левые языки этих состояний пересекаются, то есть [math]L_g(q) \cap L_g(q') = \{ w \}[/math].
По окончании процесса допуска слова [math]w[/math] мы оказываемся в состоянии [math]q[/math] или [math]q'[/math]. Следовательно, из какого-то состояния на пути в терминальное существует несколько различных переходов по одному из символов [math]w[/math], а значит [math]\mathcal{A}[/math] — НКА. Получаем противоречие.
[math]\triangleleft[/math]


Определение:
Обратное слово (англ. reverse of the word) [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].


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


Определение:
Обратный автомат (англ. reverse of the automaton) для автомата [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):
Детерминированный автомат минимален тогда и только тогда, когда правые языки его состояний различны и все состояния достижимы.
[math]\triangleright[/math]

Рассмотрим состояния [math]q[/math] и [math]q'[/math] ([math]q \neq q'[/math]) в ДКА. Пусть их правые языки [math]L_d(q) = L_d(q')[/math]. Тогда состояния [math]q[/math] и [math]q'[/math] можно объединить в одно.

Если состояние [math]q[/math] недостижимо из начального состояния [math]s[/math], то его можно удалить из автомата — это никак не повлияет на язык [math]L[/math].
[math]\triangleleft[/math]

Алгоритм[править]

Описание[править]

Алгоритм минимизации конечных автоматов Бржозовского (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]dr(\mathcal{A})[/math] — результат [math]d(r(\mathcal{A}))[/math]. Аналогично для [math]rdr(\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], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.

См. также[править]

Примечания[править]

Источники информации[править]