38
правок
Изменения
м
fixes
{{Определение
|definition=
'''Недетерминированный конечный автомат''' (НКА) {{---}} это пятерка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>, где <tex>\Sigma</tex> {{---}} алфавит, <tex>Q</tex> {{---}} множество состояний автомата, <tex>s</tex> {{---}} начальное состояние автомата, <tex>T</tex> {{---}} множество допускающих состояний автомата, <tex>\delta</tex> {{---}} функция переходов.Таким образом единственное отличие НКА от ДКА {{---}} это существование нескольких переходов по одному символу из одного состояния.
}}
{{Определение
|definition =
'''Мгновенная кофигурация''' {{---}} это пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>}}
Определим некоторые операции для мгновенных конфигураций.
[[Файл:NKA_1.jpg]]
== Алгоритм , определяющий допустимость автоматом слова == Этот алгоритм решает такую задачу: заданы НКА и слово, нужно определить допускает ли НКА данное слово. По сравнению с ДКА, определять допускает ли НКА слово сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя.
Поступим по-другому, определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex>.
* <tex> R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </tex>
accepts = False
for <tex> t \in T </tex> do
if (<tex> t \in R_{|w|} </tex>) then
accepts = True
</font>
Время работы этого алгоритма будет <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>
== См. также ==
* [[Детерминированные конечные автоматы]]
* [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
