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

Материал из Викиконспекты
Версия от 04:42, 5 октября 2010; Dolganov.vlad (обсуждение | вклад) (α версия)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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


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

Определение:
[math]L(\mathcal{A})=\{\alpha| Ǝt: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}[/math] --- язык автомата [math]\mathcal{A}[/math].


Пример


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

Память [math]|Q|^2||\Sigma|[/math].


Теорема

Теорема:
α(ДКА) = α(НКА)
Доказательство:
[math]\triangleright[/math]
proof.
[math]\triangleleft[/math]