188
правок
Изменения
Нет описания правки
Пусть <tex>\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle</tex> {{---}} [[Недетерминированные_конечные_автоматы|НКА]].<br>Тогда детерминированный автомат <tex>d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle</tex> определяется следующим образом:
* Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого <tex>q' \in Q'</tex> имеем <tex>q' \subseteq Q</tex>,
* Начальное состояние в <tex>d(\mathcal{A})</tex> {{---}} множество из <tex>I</tex> начальных состояний автомата <tex>\mathcal{A}</tex>,
* Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
* Пусть <tex>q'</tex> {{---}} состояние детерминированного автомата и <tex>a</tex> – символ из <tex>\Sigma</tex>. Если переход из <tex>q'</tex> по символу <tex>a</tex> определен, тогда, по построению: <tex>\delta'(q', a) = \bigcup\limits_{q \in q'}{ \delta(q, a)}</tex>.
{{Утверждение
|about=4
|statement=
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q \mathcal{A}</tex>, принадлежащих множеству <tex>q'</tex>.
}}
==Алгоритм==
