Изменения

'''Недетерминированный конечный автомат(НКА) ''' (англ. ''Nondeterministic finite automaton, NFA'') {{--- набор из пяти элементов }} пятёрка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to p(2^Q) \rangle</tex>, где <tex>\Sigma</tex> {{--- }} алфавит, <tex>Q</tex> {{--- }} множество состояний автомата, <tex>s</tex> {{-- -}} начальное состояние автомата, <tex>T</tex> {{-- Множество -}} множество допускающих состояний автомата, <tex>\delta</tex> {{--- }} функция переходов.Таким образом , единственное отличие НКА от [[Детерминированные_конечные_автоматы | ДКА]] {{--- это ДКА с возможностью }} существование нескольких переходов по одному символу из одного состояния.

==Процесс допуска = Язак автомата = НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.Теперь это опишем более формально.{{Определение|definition ='''Мгновенное описание''' (англ. ''snapshot'') {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.}}Определим некоторые операции для мгновенных описаний.{{Определение|definition =Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за один шаг''' (англ. ''directly yields'') из <tex>\langle q, \alpha \rangle </tex>, если:* <tex>\alpha = c\beta</tex>;* <tex>p \in \delta (q, c)</tex>.Это также записывают так: <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>.}}{{Определение|definition =[[Транзитивное замыкание#Рефлексивно-транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <tex> \vdash </tex> обозначается как <tex> \vdash^*</tex>. <br>И говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.<!--Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</tex>:* <tex>\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \vdash \langle u_{n-1}, c_n \beta\rangle \vdash \langle p, \beta \rangle</tex>. --><!--Это также записывают так: <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</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 \alpha| Ǝt\ \exists t \in T : \langle s, \alpha w \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}rbrace </tex> --- язык автомата .В этом случае также говорят, что автомат <tex>\mathcal{A}</tex> '''распознаёт''' (англ. ''recognize'') язык <tex> L </tex>.

Автомат, допускающий слова над алфавитом из символов 0 и 1, допускающий слова оканчивающиеся на 0101[[Файл:Finite state machine 4.png|600px]]

(Это НКА, который распознает язык из алфавита <tex> \lbrace 0|, 1)*0101\rbrace </tex>, где на четвертой с конца позиции стоит 0.

[[Файл:NKA_1== Алгоритм, определяющий допустимость автоматом слова =====Постановка задачи===Пусть заданы НКА и слово <tex>w</tex>. Требуется определить, допускает ли НКА данное слово.jpg]]

== Способ хранения =Алгоритм===Определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex> : <tex> R(\alpha) = \lbrace p \ | \ \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </tex>.

Срособ хранения НКА отличается от ДКА лишь темЗаметим, что если <tex> \exists t \in T : t \in R(w) </tex>, то слово допускается, так как <tex> \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle </tex> по определению <tex> R(w) </tex>. Таким образом, алгоритм состоит в ячейке таблицы хранится список состоянийтом, в которые возможен переход по данному символучтобы построить <tex> R(w) </tex>.

Память Очевидно, что <tex>|Q|^2||R(\varepsilon) = \lbrace s \rbrace </tex>. Пусть мы построили <tex> R(\alpha) </tex>, построим <tex> R(\alpha c)</tex>, где <tex> c \in \Sigma</tex>. Заметим, что <tex> R(\alpha c) = \lbrace q \ |\ q \in \delta(p, c), p \in R(\alpha) \rbrace </tex>., так как

<tex> \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle p, c \rangle \vdash \langle q, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle q, \varepsilon \rangle </tex>, <tex> \forall q \in \delta(p, c) </tex>. Теперь, когда мы научились по <tex> R(\alpha) </tex> строить <tex> R(\alpha c)</tex>, возьмем <tex> R(\varepsilon) </tex> и будем последовательно вычислять <tex>R(w[1 \ldots k])</tex> для <tex> k=1 \ldots |w| </tex>. Таким образом, мы получим <tex>R(w)</tex>, и всё, что осталось — проверить, есть ли в нём терминальное состояние. ===Псевдокод= Теорема == '''bool''' accepts(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex>: '''Automaton''', <tex>\mathtt{w}</tex>: '''String'''): <tex> R_0 = \lbrace s \rbrace </tex> '''for''' i = 1 '''to''' <tex>\mathtt{Теоремаw}</tex>.length|statement <tex> R_i =\varnothing </tex>α '''for''' (ДКА<tex> q </tex> '''in''' <tex> R_{i - 1} </tex>) <tex> R_i = αR_i \cup \delta(НКАq, \mathtt{w}[i])</tex> '''return''' <tex> R_{|\mathtt{w}|proof} \cap T \neq \varnothing </tex> Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>. == См. также ==proof* [[Детерминированные конечные автоматы]]* [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]== Источники информации ==* ''Ю. Громкович'' Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 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]] [[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]]