Изменения
добавил алгоритм преобразования
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''', если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}
== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике.
}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Ввведем функцию <tex> recursive(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>
'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>
'''function''' recursive (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRihtType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRihtType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRihtType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRihtType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>recursive(N_i) \neq self </tex>, т.к грамматика не самоприменима.
В основе алгоритма будет рекурсивный обход грамматики во все стороны. Спускаемся по грамматике до тех пор не приходим в терминал или символ алфавита:
# символ алфавит или <tex> /varepsilon </tex> {{---}} добовляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный терминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)
===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</tex> {{---}} множество переходов ДКА.
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)
'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> <font color=green>// пришли в лист дерева разбора</font>
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if recursive'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' <font color=green>// рекурсивный нетерминал rihgt или self</font>
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)
