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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 3 участников)
Строка 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> сменой местами начальных и конечных состояний и сменой направлений переходов.
 
}}
 
}}
  
Строка 62: Строка 66:
 
{{Определение
 
{{Определение
 
|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>.
 
}}
 
}}
  
Строка 75: Строка 79:
 
|about=5
 
|about=5
 
|statement=
 
|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>.
 
}}
 
}}
  
Строка 85: Строка 92:
 
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
 
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
  
Пусть <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>\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>.
  
 
{{Теорема
 
{{Теорема
Строка 92: Строка 102:
 
|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|Заключительный шаг]]
  
 
== Заключение ==
 
== Заключение ==
Строка 114: Строка 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 Пётр Советов {{---}} Алгоритм Бржозовского для минимизации конечного автомата]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Минимизация ДКА]]

Текущая версия на 19:29, 4 сентября 2022

Задача:
Пусть дан автомат [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], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.

См. также

Примечания

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