3622
правки
Изменения
м
Введем Определим функцию <tex> \mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {left, right, self, cycle\typeRecursive} </tex>: '''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>: '''nonterminal'''):'''typeRecurcive''' '''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 ''' right; '''if''' (isLeftType(<tex>N_i</tex>) && '''and''' isRightType(<tex>N_i</tex>) '''return ''' self; '''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>, т.к в противном случае грамматика будет самоприменима.
→Идея алгоритма
{{Лемма
|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> N^* </tex> множество рекурсивных терминалов нетерминалов из <tex> N </tex>. Пусть, <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> '''functionbool''' 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>
'''functionbool''' 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>
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ Символ алфавит или <tex> \varepsilon </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>)
'''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 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 \cdots ldots X_m, q_C</tex>) '''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...\ldots X_m \land X_1,...\ldots X_m \neq N_i </tex> makeFA (<tex>q_D, X_1 \cdots ldots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' <font color=green>// рекурсивный нетерминал right или cyclic</font>
'''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_C, X_1 \cdots ldots X_m, q_1</tex>) '''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...\ldots X_m \land X_1,...\ldots X_m \neq N_i </tex> makeFA (<tex>q_D, X_1 \cdots ldots 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>)
== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации: <tex>\mathrm {RTN }</tex> (''recursive transition network'') аппроксимацию и <tex>\mathrm {MN }</tex> (''Mohri and Nederhof's'') аппроксимацию — самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots ldots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots ldots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdotsldots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| mid A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.
===MN аппроксимация ===
Построим по данной самоприменимой контекстно-свободной грамматике <tex> G </tex> регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots ldots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdotsldots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots ldots B_m , B_1^* \cdots ldots B_m^*</tex> и следуюшие правила: <tex> \begin{cases} A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots ldots \\ B^*_m \rightarrow {\alpha}_m A^* \end{cases}</tex>.<br /> :(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrixcases} A \rightarrow \alpha B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrixcases}\right.\Rightarrow G^* = \left\{\begin{matrixcases} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrixcases}\right.</tex><br/>Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | \mid n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. <br/><br/>
=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. <br/> Привлекателным свойством <tex>\mathrm {MN }</tex> аппроксимации по сравнению с <tex>\mathrm {RTN}</tex>, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для <tex>\mathrm {RTN }</tex> апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик.<br/>
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.
== См. также ==
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
* [[Замкнутость регулярных языков относительно различных операций]]
* [[Основные определения, связанные со строками]]
* [[Замкнутость КС-языков относительно различных операций]]
== Примечания ==
<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
[[Категория: Теория формальных языков]]
[[Категория: Базовые понятия о грамматиках]]
[[Категория: Контекстно-свободные грамматики]]
