Изменения

Перейти к: навигация, поиск

Алгоритм Бржозовского

212 байт добавлено, 19:15, 29 октября 2016
Нет описания правки
|statement=
Правый язык состояния <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>.
}}
* начальное состояние {{---}} <tex>L</tex>,
* терминальные состояния {{---}} множество отношений, содержащих пустое слово,
* функция перехода <tex>\delta(u^{-1} \cdot L, x) = (ux)^{-1} \cdot L</tex>.
Автомат <tex>\mathcal{A}_L</tex> уникален с точностью до изоморфизма и имеет минимальное количество состояний.
|about=5
|statement=
Автомат Детерминированный полный достижимый автомат минимален тогда и только тогда, когда правые языки его состояний различны.
}}
===Описание===
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
 
* Он элегантен и весьма оригинален.
* Он эффективен.
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
Обладая обычными процедурами обращения Пусть <tex>\operatornamemathcal{revA}</tex> и детерминизации {{---}} конечный автомат. <tex>d(\operatornamemathcal{detA})</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>. Для этого надо дважды провести его через обе вышеуказанные процедуры:
{{Теорема|about=Бржозовский, 1962|statement=Пусть <tex>mFA = \operatorname mathcal{detA}(\operatorname</tex> {rev}(\operatorname{det---}(\operatorname{r}автомат (FA)))необязательно детерминированный)</tex>, где * распознающий язык <tex>FAL</tex> это исходный КА,* . Минимальный детерминированный автомат <tex>\operatornamemathcal{revA}_L</tex> это процедура обращения КА,* может быть вычислен следующим образом: <tex>\operatornamemathcal{A}_L = drdr(\mathcal{detA})</tex> это процедура детерминизации КА,* <tex>mFA</tex> это минимизированный КА==|proof=Корректность===По построению автомат 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) минимальный.
}}
===Пример работы===
# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>):<br>[[Файл:Fa.png|Исходный НКА]]
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>):<br>[[Файл:Rfa.png|Первый шаг]]
188
правок

Навигация