18
правок
Изменения
α версия
== Недетерминированный конечный автомат ==
{{Определение
|definition=
Недетерминированный конечный автомат(НКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to p(Q) \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
Таким образом НКА - это ДКА с возможностью нескольких переходов по одному символу из одного состояния.
}}
=== Язак автомата ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| Ǝt: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}
== Пример ==
*******
== Способ хранения ==
**********
Память <tex>|Q|^2||\Sigma|</tex>.
== Теорема ==
{{Теорема
|statement=
α(ДКА) = α(НКА)
|proof=
proof.
}}
{{Определение
|definition=
Недетерминированный конечный автомат(НКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to p(Q) \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
Таким образом НКА - это ДКА с возможностью нескольких переходов по одному символу из одного состояния.
}}
=== Язак автомата ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| Ǝt: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}
== Пример ==
*******
== Способ хранения ==
**********
Память <tex>|Q|^2||\Sigma|</tex>.
== Теорема ==
{{Теорема
|statement=
α(ДКА) = α(НКА)
|proof=
proof.
}}
