1632
правки
Изменения
м
===MT аппроксимация ===
Построим, по данной самоприменимой кс грамматике <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 B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>.<br />(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
rollbackEdits.php mass rollback
{{Лемма
|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> getTheTypeOfMutualRecursiveSet\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 \rightarrow varepsilon ]</tex>. Аналогично определим функцию <tex>\mathtt {leftisRightType}(N_i)</tex>, rightкоторая возвращает <tex>true</tex>, self, cycleесли существует <tex> (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \} varepsilon ]</tex>: '''functionbool''' IsLeftTypeisLeftType(<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''' IsRightTypeisRightType(<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>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {typeRecursive} </tex>: '''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>: '''nonterminal'''):'''typeRecurcive''' '''if''' !IsLeftTypeisLeftType(<tex>N_i</tex>) && IsRightType'''and''' isRightType(<tex>N_i</tex>) '''return ''' left; '''if''' IsLeftTypeisLeftType(<tex>N_i</tex>) && '''and''' !IsRightTypeisRightType(<tex>N_i</tex>) '''return ''' right; '''if''' (IsLeftTypeisLeftType(<tex>N_i</tex>) && IsRightType'''and''' isRightType(<tex>N_i</tex>) '''return ''' self; '''if''' !IsLeftTypeisLeftType(<tex>N_i</tex>) && '''and''' !IsRightTypeisRightType(<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>, т.к в противном случае грамматика будет самоприменима.<br \>
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ Символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат;# нерекурсивный Нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает;# рекурсивный Рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода).
===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</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>// рекурсивный нетерминал rihgt 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>]]
=== RTN аппроксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
[[Файл:RTN_Automat1.png|280px|thumb|leftright|Конечный автомат для грамматики
<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} \ldots B_m {\alpha}_{m}</tex>, где <tex> B_1, \ldots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \ldots B_m , B_1^* \ldots B_m^*</tex> и следуюшие правила: <tex>\begin{cases} A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \ldots \\ B^*_m \rightarrow {\alpha}_m A^* \end{cases}</tex>.
:(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrixcases} A \rightarrow \alpha A 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}</tex> Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n \mid n > 0\right}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. === Сравнение двух методов ===Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. Привлекателным свойством <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>, что может быть критично для аппроксимации больших грамматик.Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках. == См. также ==* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]* [[Замкнутость регулярных языков относительно различных операций]]* [[Основные определения, связанные со строками]]* [[Замкнутость КС-языков относительно различных операций]]
== Источники Примечания ==* [http:<references//books.google.ru/books?id=gvVK07D4wwUC&pg=PA161&lpg=PA161 книга, где можно узнать много нового про аппроксимации]* [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 Разобрано много примеров аппроксимаций]>
== Источники информации==*''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%2Facl2Fwww.ldccs.upennucsb.edu%2FJ2F~omer%2FJ002FDOWNLOADABLE%2FJ002Fcfg-1003reg09.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQAQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaAAFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=UF88aXWRAbapv4o_UrIjGg_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
[[Категория: Теория формальных языков]]
[[Категория: Базовые понятия о грамматиках]]
[[Категория: Контекстно-свободные грамматики]]
