308
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Недетерминированный конечный автомат(НКА)''' или НКА (англ. ''Nondeterministic finite automaton, NFA {{---}} Nondeterministic Finite Automaton'') {{---}} пятёрка <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 =
'''Мгновенное описание''' (англ. ''snapshot'') {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.
}}
{{Определение
|definition =
НКА '''допускает''' (англ. ''accepts'') слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
}}
|definition =
Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>.
* <tex>L(\mathcal{A}) = \lbrace w \ | \ \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace </tex>.В этом случае также говорят, что автомат <tex> \mathcal{A} </tex> '''распознаёт''' (англ. ''recognize'') язык <tex> L </tex>.
}}
===Псевдокод===
<font color=darkgreen>// Строим <tex> R_i </tex> </font>
<tex> R_0 = \lbrace s \rbrace </tex>
'''for ''' i = 1 '''to ''' <tex>\mathtt{w}</tex>.length(w) do
<tex> R_i = \varnothing </tex>
'''for ''' (<tex> q </tex> p \'''in ''' <tex> R_{i - 1} </tex> do) <tex> R_i = R_i \cup \delta(pq, \mathtt{w}[i]) </tex> <font color=darkgreen>// Проверяем, есть ли среди <tex> R_n </tex> терминальные состояния </font> accepts = False''false'' '''for ''' (term_state '''in''' <tex> t \in T </tex> do) '''if ''' term_state '''in''' <tex> t \in R_{|\mathtt{w}|} </tex> accepts = True''true''
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
* [[Детерминированные конечные автоматы]]
* [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
== Литература Источники информации ==
* ''Ю. Громкович'' Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 2010. — С. 87. — ISBN 978-5-9775-0406-5
* ''John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman'' Introduction to Automata Theory, Languages, and Computation. Second edition. P. 71. ISBN 0-201-02988-X
* [[wikipedia:en:Nondeterministic finite automaton | Wikipedia {{---}} Nondeterministic finite automaton]]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
