3622
правки
Изменения
м
Введем Определим функцию <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {left, right, self, cycle\typeRecursive} </tex>: '''function''' getTheTypeOfMutualRecursiveSet(<tex>N_i</tex>: '''nonterminal'''):'''typeRecurcive'''
→Идея алгоритма
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства приведем рассмотрим алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Также приведем ссылку на формальное доказательство<ref>[http://booksac.googleels-cdn.rucom/booksS0019995859800176/1-s2.0-S0019995859800176-main.pdf?id_tid=tFvtwGYNe7kC01067c30-c616-11e6-a178-00000aab0f6c&pgacdnat=PA21#v=onepage&q&f=false формальное доказательство1482171029_8a3a81a6f520cf0f9a769aaafbb8babb Noam Chomsky {{---}} A note on phrase structure grammars]</ref>.
}}
Пусть, <tex> P = \{N_1,N_2,\ldots,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных нетерминалов,
<tex> N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i</tex> <tex> N_i \neq \emptyset </tex>.
Определим вспомогательную функцию <tex>\mathtt {isLeftType}(N_i)</tex>, которая возвращает <tex>true</tex>, если существует <tex> (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>. Аналогично определим функцию <tex>\mathtt {isRightType}(N_i)</tex>, которая возвращает <tex>true</tex>, если существует <tex> (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex> '''bool''' isLeftType(<tex>N_i</tex>: '''nonterminal'''):
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>
'''bool''' isRightType(<tex>N_i</tex>: '''nonterminal'''):
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>
Будем называть <tex>\mathtt {typeRecursive}</tex> набор четырех величин <tex>\{left, right, self, cycle\} </tex>
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)
'''return''' left
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)
'''return''' cyclic
:Состояние <tex> left</tex> означает, что <tex> N_i </tex> состоит только из лево-рекурсивных нетерминалов.
:Состояние <tex> right</tex> означает, что <tex> N_i </tex> состоит только из право-рекурсивных нетерминалов.
:Состояние <tex> cyclic</tex> означает, что <tex> N_i </tex> состоит только из правил, участвующих в рекурсии.
:Состояние <tex> self</tex> означает, что <tex>i </tex> такое, при котором грамматика самоприменима.
Заметим, что <tex> \forall i </tex> <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G: '''grammar'''): '''Automaton''' <font color=green>// <tex> G = \langle N, \Sigma, P, S \rangle</tex> </font>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState() <font color=green>// createState создает некоторый объект, не принадлежащий <tex>Q</tex>, возвращает этот объект и добавляет его в <tex>Q</tex> </font> f = createState()
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA(s,S,f)
'''function''' makeFA(q0: '''vertex''',a: '''char''',q1: '''vertex'''):'''Automaton''' '''if''' a == <tex> \varepsilon </tex> || '''or''' 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>)
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if getTheTypeOfMutualRecursiveSet'''getTheTypeOfMutualRecursiveSet(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i </tex>
makeFA(<tex>q_0, X_1 \ldots X_m, q_C</tex>)
* [[Основные определения, связанные со строками]]
* [[Замкнутость КС-языков относительно различных операций]]
== Примечания ==
<references/>
== Источники информации==
*''Jean-Claude Junqua,Gertjan van Noord'' — Robustness in Language and Speech Technology — Kluwer Academic Publishers, 2001 — ISBN 0-7923-6790-1
* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.ucsb.edu%2F~omer%2FDOWNLOADABLE%2Fcfg-reg09.pdf&ei=AQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=_2iZj4Xexe6-p5Cyt-GEMg&bvm=bv.59568121,d.bGE Strongly Regular Grammars and Regular Approximation of Contex-Free Languages]
* [http://www.ensani.ir/storage/Files/20101126180227-431.pdf Practical Experiments with Regular Approximation of Context-Free Languages]
*''Willem J. M. Levelt'' — An Introduction to the Theory of Formal Languages and Automata — John Benjamin B.V., 2008 — ISBN 978-90-272-3250-2
