Изменения

'''Недетерминированный конечный автомат(НКА)''' (НКАангл. ''Nondeterministic finite automaton, NFA'') {{---}} пятерка пятёрка <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> {{---}} функция переходов.Таким образом , единственное отличие НКА от [[Детерминированные_конечные_автоматы | ДКА ]] {{---}} существование нескольких переходов по одному символу из одного состояния.

'''Мгновенная кофигурацияМгновенное описание''' (англ. ''snapshot'') {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.}} Определим некоторые операции для мгновенных конфигурацийописаний.

Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за один шаг''' (англ. ''directly yields'') из <tex>\langle q, \alpha \rangle </tex>, если:* <tex>\alpha = c\beta</tex>;

Это также записывают так: <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>.

[[Транзитивное замыкание#Рефлексивно-транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <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 nc_1, c_2 \ldots c_n</tex>:* <tex>\langle q, c_1 c_2 c_3 ...\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>. -->

НКА '''допускает''' (англ. ''accepts'') слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.

* <tex> \mathcal{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>.

Язык НКА тоже является автоматным языком, так как для любого НКА можно [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|построить из НКА эквивалентный ему ДКА]], поэтому а значит, вычислительная мощность этих двух автоматов совпадает.

[[Файл:NFAFinite state machine 4.png|600px]]

Этот алгоритм решает такую задачу: ===Постановка задачи===Пусть заданы НКА и слово<tex>w</tex>. Требуется определить, нужно определить допускает ли НКА данное слово. По сравнению с ДКА, определять допускает ли НКА слово сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя. Поступим по-другому, определим ===Алгоритм===Определим множество всех достижимых состояний из стартового по слову <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> 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> w </tex>. Заметим\langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, что если <tex> \exists t alpha c \rangle \in T : t vdash^* \in R(w) </tex>langle p, то слово допускаетсяc \rangle \vdash \langle q, так как <tex> \varepsilon \rangle \Rightarrow \langle s, w \alpha c \rangle \vdash^* \langle tq, \varepsilon \rangle </tex> по определению , <tex> R\forall q \in \delta(w) </tex>. Алгоритм состоит в томp, чтобы построить <tex> R(wc) </tex>.

ОчевидноТеперь, что когда мы научились по <tex> R(\varepsilonalpha) = \lbrace s \rbrace </tex>. Пусть мы построили строить <tex> R(\alphac) </tex>, как же получить возьмем <tex> R(\alpha cvarepsilon)</tex>, где <tex> c \in \Sigma </tex>. Заметим, что * и будем последовательно вычислять <tex> R(w[1 \alpha cldots k]) = \lbrace q | q \in \delta(p, c), p \in R(\alpha) \rbrace </tex>, так как * для <tex> k=1 \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) ldots |w| </tex>.

ТеперьТаким образом, когда мы научились добавлять символ к строке, возьмем получим <tex> R(\varepsilonw) </tex>, будем добавлять <tex> w_1и всё, что осталось — проверить, w_2 \ldots w_{|w|} </tex> и находить для каждого <tex> R(w_1\ldots w_k) </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 <tex> R_i = \varnothing </tex> '''for''' (<tex> q </tex> '''in''' <tex> R_{i - 1} </tex> R) <tex> R_i = R_i \cup \delta(q, \mathtt{w}[i]) </tex>, проверим что в нем есть терминальное состояние. '''return''' <tex> R_{|\mathtt{w}|} \cap T \neq \varnothing </tex>

ПсевдокодВремя работы алгоритма:<font size = 3> <tex> R_0 = \lbrace s \rbrace </tex> for i = 1 to lengthmathop O(|w) do <tex> R_i = |\sum\varnothing </tex> for <tex> p limits_{t \in R_Q} \sum\limits_{i - 1c \in \Sigma} </tex> do <tex> R_i = R_i \cup |\delta(pt, w_ic) </tex> accepts = False for <tex> t \in T </tex> do if <tex> t \in R_{|w|} ) </tex> then accepts = True</font>.