308
правок
Изменения
Псевдокод обернул в функцию
{{Определение
|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>.
|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>. -->
===Алгоритм===
Определим множество всех достижимых состояний из стартового по слову <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> \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>.
===Псевдокод===
'''bool''' accepts(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex>: '''Automata''', <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 <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> <font color=darkgreen>// Проверяем, есть ли среди в <tex> R_n </tex> терминальные состояния </font> accepts = ''false'' '''for''' (term_state '''in''' <tex> T </tex>) '''if''' term_state '''in''' <tex> R_{|\mathtt{w}|} </tex> accepts = '''return''' ''true'' '''return''' ''false''
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
