308
правок
Изменения
м
<font color=darkgreen>// Проверяем, есть ли в <tex> R_n </tex> терминальные состояния </font> '''for''' (term_state '''in''' <tex> T </tex>) '''if''' term_state '''inreturn''' <tex> R_{|\mathtt{w}|} \cap T \neq \varnothing </tex> '''return''' ''true'' '''return''' ''false''
Нет описания правки
НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.
Теперь это опишем более формально.
{{Определение
|definition =
'''Мгновенное описание''' (англ. ''snapshot'') {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</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, \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>.
}}
== Язык автомата ==
<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 w[k])</tex> для <tex>k=1..\ldots |w|</tex>.
Таким образом, мы получим <tex>R(w)</tex>, и всё, что осталось — проверить, есть ли в нём терминальное состояние.
===Псевдокод===
'''bool''' accepts(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex>: '''AutomataAutomaton''', <tex>\mathtt{w}</tex>: '''String'''): <font color=darkgreen>// Строим <tex> R_i </tex> </font>
<tex> R_0 = \lbrace s \rbrace </tex>
'''for''' i = 1 '''to''' <tex>\mathtt{w}</tex>.length
'''for''' (<tex> q </tex> '''in''' <tex> R_{i - 1} </tex>)
<tex> R_i = R_i \cup \delta(q, \mathtt{w}[i]) </tex>
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
