Изменения

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

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

1645 байт добавлено, 00:55, 29 октября 2016
Нет описания правки
}}
Минимальный автомат <tex>\mathcal{A_L}</tex> для регулярного языка <tex>L</tex> определяется следующим образом:
* множество состояний {{---}} это множество левых отношений языка <tex>L</tex>,
* начальное состояние {{---}} <tex>L</tex>,
* терминальные состояния {{---}} множество отношений, содержащих пустое слово,
* функция перехода <tex>\delta(u^-1 * L, x) = (ux)^-1 \cdot L</tex>
Автомат <tex>\mathcal{A_L}</tex> уникален с точностью до изоморфизма и имеет минимальное количество состояний.
{{Утверждение
|about=5
|statement=
Автомат минимален тогда и только тогда, когда правые языки его состояний различны.
}}
==Алгоритм==
Обладая обычными процедурами обращения <tex>\operatorname{rev}</tex> и детерминизации <tex>\operatorname{det}</tex> конечного [[Детерминированные конечные автоматы|автомата]], мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного [[Детерминированные конечные автоматы|автомата]]. Для этого надо дважды провести его через обе вышеуказанные процедуры:
<tex>mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{revr}(FA))))</tex>, где
* <tex>FA</tex> это исходный КА,
===Корректность===
Корректность алгоритма доказана в работе<ref>[http://wwwПо построению автомат drdr(A) конечный.researchgateСогласно утверждению 2, он распознает язык L. Покажем, что правые языки drdr(A) все различны. Из утверждения 1, левые языки dr(A) попарно не пересекаются. Из утверждения 3, правые языки rdr(A) являются левыми языками dr(A). Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык drdr(A) – объединение правых языков rdr(A). Поскольку правые языки rdr(A) попарно не пересекаются, все правые языки drdr(A) различны. Тогда, согласно утверждению 5 автомат drdr(A) минимальный.net/publication/255626373_Split_and_join_for_minimizing__Brzozowski's_algorithm Split and join for minimizing : Brzozowski's algorithm]</ref>
==Пример работы==
188
правок

Навигация