Недетерминированные конечные автоматы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Язак автомата)
м (Недетерминированный конечный автомат)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|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> -- функция переходов.
+
Недетерминированный конечный автомат(НКА) --- набор из пяти элементов <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> -- функция переходов.
Таким образом НКА - это ДКА с возможностью нескольких переходов по одному символу из одного состояния.
+
Таким образом НКА - это автомат с возможностью нескольких переходов по одному символу из одного состояния.
 
}}
 
}}
  

Версия 03:43, 13 октября 2010

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

Определение:
Недетерминированный конечный автомат(НКА) --- набор из пяти элементов [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| \exists t: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}[/math] --- язык автомата [math]\mathcal{A}[/math].


Пример

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

(0|1)*0101

NKA 1.jpg

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

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

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