Изменения
сделано несколько исправлений
{{Определение
|definition=
Недетерминированный конечный автомат(НКА) {{--- набор из пяти элементов }} это пятерка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to P(2^Q) \rangle</tex>, где <tex>\Sigma</tex> {{-- -}} алфавит, <tex>Q</tex> {{-- -}} множество состояний автомата, <tex>s</tex> {{-- -}} начальное состояние автомата, <tex>T</tex> {{-- Множество -}} множество допускающих состояний автомата, <tex>\delta</tex> {{--- }} функция переходов.Таким образом единственное отличие НКА от ДКА {{--- }} это автомат с возможностью существование нескольких переходов по одному символу из одного состояния.
}}
== Процесс допуска ==
Определим некоторые обозначенияя для НКА:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если:
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>
Автомат допускает слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
Процесс допуска происходит так же, как в ДКА, в котором Мерлин помогает выбрать правильный переход.
{{Определение
|definition=
Память <tex>|Q|^2||\Sigma|</tex>.
==См. также==
* [[Детерминированные конечные автоматы]]
