Недетерминированные конечные автоматы

Недетерминированный конечный автомат

Определение:

Недетерминированный конечный автомат(НКА) --- набор из пяти элементов $\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to p(Q) \rangle$, где $\Sigma$ -- алфавит, $Q$ -- множество состояний автомата, $s$ -- начальное состояние автомата, $T$ -- Множество допускающих состояний автомата, $\delta$ -- функция переходов. Таким образом НКА - это ДКА с возможностью нескольких переходов по одному символу из одного состояния.

Язак автомата

Определение:

$L(\mathcal{A})=\{\alpha| Ǝt: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}$ --- язык автомата $\mathcal{A}$.

Пример

Автомат, допускающий слова над алфавитом из символов 0 и 1, допускающий слова оканчивающиеся на 0101.

(0|1)*0101

Способ хранения

Срособ хранения НКА отличается от ДКА лишь тем, что в ячейке таблицы хранится список состояний, в которые возможен переход по данному символу.

Память $|Q|^2||\Sigma|$.

Теорема

Теорема:

α(ДКА) = α(НКА)

Доказательство:

$\triangleright$

proof.

$\triangleleft$