188
правок
Изменения
Нет описания правки
|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) выделяется, по крайней мере, следующими качествами:
* Он элегантен и весьма оригинален.
* Он эффективен.
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
{{Теорема|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|Первый шаг]]
