188
правок
Изменения
Нет описания правки
}}
Минимальный автомат <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> это исходный КА,
===Корректность===
==Пример работы==
