Регулярная аппроксимация КС-языков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример)
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 3 участников)
Строка 18: Строка 18:
 
{{Лемма
 
{{Лемма
 
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
 
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Также приведем ссылку на [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21#v=onepage&q&f=false формальное доказательство].
+
|proof = В качестве конструктивного доказательства рассмотрим алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Также приведем ссылку на формальное доказательство<ref>[http://ac.els-cdn.com/S0019995859800176/1-s2.0-S0019995859800176-main.pdf?_tid=01067c30-c616-11e6-a178-00000aab0f6c&acdnat=1482171029_8a3a81a6f520cf0f9a769aaafbb8babb Noam Chomsky {{---}} A note on phrase structure grammars]</ref>.
  
 
}}
 
}}
 
=== Идея алгоритма ===
 
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.  
+
Пусть, <tex> N^* </tex> множество рекурсивных нетерминалов из <tex> N </tex>.  
Пусть, <tex> P = \{N_1,N_2,\ldots,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </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> N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i</tex> <tex> N_i \neq \emptyset </tex>.  
  '''function''' isLeftType(<tex>N_i</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>
 
     '''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>):
+
  '''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>
 
     '''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> getTheTypeOfMutualRecursiveSet(N_i): P \rightarrow  \{left, right, self, cycle\}  </tex>:
+
Определим функцию <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow  \mathtt {typeRecursive}  </tex>:
  '''function''' getTheTypeOfMutualRecursiveSet(<tex>N_i</tex>):
+
  '''function''' getTheTypeOfMutualRecursiveSet(<tex>N_i</tex>: '''nonterminal'''): '''typeRecurcive'''
     '''if''' !isLeftType(<tex>N_i</tex>) && isRightType(<tex>N_i</tex>)  
+
     '''if''' !isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)  
 
         '''return''' left
 
         '''return''' left
     '''if''' isLeftType(<tex>N_i</tex>) && !isRightType(<tex>N_i</tex>)  
+
     '''if''' isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)  
 
         '''return''' right
 
         '''return''' right
     '''if''' (isLeftType(<tex>N_i</tex>) && isRightType(<tex>N_i</tex>)  
+
     '''if''' isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)  
 
         '''return''' self
 
         '''return''' self
     '''if''' !isLeftType(<tex>N_i</tex>) && !isRightType(<tex>N_i</tex>)  
+
     '''if''' !isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)  
 
         '''return''' cyclic
 
         '''return''' cyclic
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
+
:Состояние <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> \varepsilon </tex> {{---}} добавляем новое правило в автомат;
 
# Символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат;
Строка 53: Строка 62:
  
 
<tex>T</tex> {{---}} множество допускающих состояний.
 
<tex>T</tex> {{---}} множество допускающих состояний.
  '''function''' createFA(G):              <font color=green>// <tex> G = \langle N, \Sigma, P, S \rangle</tex> </font>
+
  '''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>\mathtt{Q} \leftarrow \varnothing</tex>
 
     <tex>\Delta \leftarrow \varnothing </tex>
 
     <tex>\Delta \leftarrow \varnothing </tex>
     s = createState
+
     s = createState()              <font color=green>// createState создает некоторый объект, не принадлежащий <tex>Q</tex>, возвращает этот объект и добавляет его в <tex>Q</tex>  </font> 
     f = createState
+
     f = createState()
 
     <tex>F \leftarrow \{f\} </tex>
 
     <tex>F \leftarrow \{f\} </tex>
 
     '''return''' makeFA(s,S,f)
 
     '''return''' makeFA(s,S,f)
 
        
 
        
  '''function''' makeFA(q0,a,q1):
+
  '''function''' makeFA(q0: '''vertex''', a: '''char''', q1: '''vertex'''): '''Automaton'''
     '''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex>            <font color=green>// пришли в лист дерева разбора</font>
+
     '''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>
 
         <tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
 
         '''return'''
 
         '''return'''
 
     '''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>   
 
     '''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
+
         q = createState()
 
         makeFA(<tex>q_0,X,q_1</tex>)
 
         makeFA(<tex>q_0,X,q_1</tex>)
 
         makeFA(<tex>q, \beta, q_1 </tex>)
 
         makeFA(<tex>q, \beta, q_1 </tex>)
Строка 73: Строка 82:
 
           '''foreach''' b '''in''' <tex>N_i</tex>  
 
           '''foreach''' b '''in''' <tex>N_i</tex>  
 
             <tex>q_b</tex> = createState
 
             <tex>q_b</tex> = createState
           '''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
+
           '''if''' 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>
 
             '''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>)             
 
                 makeFA(<tex>q_0, X_1 \ldots X_m, q_C</tex>)             
Строка 90: Строка 99:
  
 
== Аппроксимации самоприменимой грамматики ==
 
== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации: RTN (recursive transition network) аппроксимацию и MN (Mohri and Nederhof's) аппроксимацию — самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</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> для грамматики   
 
[[Файл: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>]]  
Строка 98: Строка 107:
 
  <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</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
+
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \ldots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \ldots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \ldots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| 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>.
+
#Таким образом мы построили множество конечных автоматов <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 аппроксимация ===
 
===MN аппроксимация ===
 
Построим по данной самоприменимой контекстно-свободной грамматике <tex> G </tex> регулярную грамматику <tex> G^*</tex>.
 
Построим по данной самоприменимой контекстно-свободной грамматике <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 \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>).
+
#Для каждого правила <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^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
 
==== Пример ====
 
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha B \alpha  
+
<tex> G = \begin{cases} A \rightarrow \alpha B \alpha  
 
\\ B \rightarrow \beta A | \beta
 
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B   
+
\end{cases}\Rightarrow
 +
G^* = \begin{cases} A \rightarrow \alpha B   
 
\\ A^* \rightarrow B^* | \varepsilon
 
\\ A^* \rightarrow B^* | \varepsilon
 
\\ B \rightarrow \beta A | \beta B^*
 
\\ B \rightarrow \beta A | \beta B^*
 
\\ B^* \rightarrow \alpha A^* | \varepsilon
 
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
+
\end{cases}</tex>
<br/>Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n \mid n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. <br/><br/>
+
 
 +
Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n \mid n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>.
  
 
=== Сравнение двух методов ===
 
=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. <br/>
+
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой.  
Привлекателным свойством MN аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации  больших грамматик.<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>, что может быть критично для аппроксимации  больших грамматик.
 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.
 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.
 +
 +
== См. также ==
 +
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 +
* [[Замкнутость регулярных языков относительно различных операций]]
 +
* [[Основные определения, связанные со строками]]
 +
* [[Замкнутость КС-языков относительно различных операций]]
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации==
 
== Источники информации==
 
*''Jean-Claude Junqua,Gertjan van Noord'' — Robustness in Language and Speech Technology — Kluwer Academic Publishers, 2001 — ISBN 0-7923-6790-1
 
*''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]
 
* [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
 
*''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
  
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 +
[[Категория: Базовые понятия о грамматиках]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]

Текущая версия на 19:21, 4 сентября 2022


Определения

Определение:
Контекстно-свободная грамматика [math] G = \langle N, \Sigma, P, S \rangle[/math] называется самоприменимой (англ. self-embeded), если [math] \exists A \in N: A \Rightarrow^* \alpha A \beta[/math], [math] \alpha \neq \varepsilon \land \beta \neq \varepsilon [/math] .


Определение:
Нетерминал [math] A \in N[/math] в грамматике [math] G = \langle N, \Sigma, P, S \rangle[/math] называется рекурсивным (англ. recursive), если [math] \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta[/math] .


Определение:
Нетерминалы [math] A,B \in N[/math] в грамматике [math] G = \langle N, \Sigma, P, S \rangle[/math] называются взаимно рекурсивными (англ. mutual recursive), если [math] \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[/math] .


Алгоритм преобразования грамматики в конечный автомат

Лемма:
Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
Доказательство:
[math]\triangleright[/math]
В качестве конструктивного доказательства рассмотрим алгоритм построения конечного автомата по грамматике. Также приведем ссылку на формальное доказательство[1].
[math]\triangleleft[/math]

Идея алгоритма

Пусть, [math] N^* [/math] множество рекурсивных нетерминалов из [math] N [/math]. Пусть, [math] P = \{N_1,N_2,\ldots,N_K\} [/math] разбиение [math] N^*[/math] на [math] k [/math] дизъюнктных множеств взаимно рекурсивных нетерминалов, [math] N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i[/math] [math] N_i \neq \emptyset [/math].

Определим вспомогательную функцию [math]\mathtt {isLeftType}(N_i)[/math], которая возвращает [math]true[/math], если существует [math] (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ][/math].

Аналогично определим функцию [math]\mathtt {isRightType}(N_i)[/math], которая возвращает [math]true[/math], если существует [math] (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ][/math]

bool isLeftType([math]N_i[/math]: nonterminal): 
    return [math] \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ][/math]

bool isRightType([math]N_i[/math]: nonterminal): 
    return [math] \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ][/math]

Будем называть [math]\mathtt {typeRecursive}[/math] набор четырех величин [math]\{left, right, self, cycle\} [/math]

Определим функцию [math]\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {typeRecursive} [/math]:

function getTheTypeOfMutualRecursiveSet([math]N_i[/math]: nonterminal): typeRecurcive
   if !isLeftType([math]N_i[/math]) and isRightType([math]N_i[/math]) 
       return left
   if isLeftType([math]N_i[/math]) and !isRightType([math]N_i[/math]) 
       return right
   if isLeftType([math]N_i[/math]) and isRightType([math]N_i[/math]) 
       return self
   if !isLeftType([math]N_i[/math]) and !isRightType([math]N_i[/math]) 
       return cyclic
Состояние [math] left[/math] означает, что [math] N_i [/math] состоит только из лево-рекурсивных нетерминалов.
Состояние [math] right[/math] означает, что [math] N_i [/math] состоит только из право-рекурсивных нетерминалов.
Состояние [math] cyclic[/math] означает, что [math] N_i [/math] состоит только из правил, участвующих в рекурсии.
Состояние [math] self[/math] означает, что [math]i [/math] такое, при котором грамматика самоприменима.

Заметим, что [math] \forall i [/math] [math]\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) \neq self [/math], т.к в противном случае грамматика будет самоприменима. В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:

  1. Символ алфавит или [math] \varepsilon [/math] — добавляем новое правило в автомат;
  2. Нерекурсивный нетерминал — запускаемся от всех правых частей правил, который терминал порождает;
  3. Рекурсивный нетерминал — в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода).

Псевдокод

[math]Q[/math] — множество состояний ДКА.

[math]\Delta[/math] — множество переходов ДКА.

[math]T[/math] — множество допускающих состояний.

function createFA(G: grammar): Automaton              // [math] G = \langle N, \Sigma, P, S \rangle[/math] 
    [math]\mathtt{Q} \leftarrow \varnothing[/math]
    [math]\Delta \leftarrow \varnothing [/math]
    s = createState()               // createState создает некоторый объект, не принадлежащий [math]Q[/math], возвращает этот объект и добавляет его в [math]Q[/math]    
    f = createState()
    [math]F \leftarrow \{f\} [/math]
    return makeFA(s,S,f)
     
function makeFA(q0: vertex, a: char, q1: vertex): Automaton
   if a == [math] \varepsilon [/math] or a [math] \in \Sigma[/math]             // пришли в лист дерева разбора
        [math] \Delta = \Delta \cup \{(q_0,a,q_1)\} [/math]
        return
   if a == [math]X\beta[/math] where [math] X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| \gt  0 [/math]  
        q = createState()
        makeFA([math]q_0,X,q_1[/math])
        makeFA([math]q, \beta, q_1 [/math])
        return
    if exist [math] N_i [/math] where [math] a \in N_i [/math]  
         foreach b in [math]N_i[/math] 
            [math]q_b[/math] = createState
         if getTheTypeOfMutualRecursiveSet([math] N_i [/math]) == left 
            foreach C in [math]N_i[/math] where [math] C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i [/math]
               makeFA([math]q_0, X_1 \ldots X_m, q_C[/math])             
            foreach C,D in [math]N_i[/math] where [math] C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i [/math]
               makeFA([math]q_D, X_1 \ldots X_m, q_C[/math])
               [math] \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} [/math]
          else                      // рекурсивный нетерминал right или cyclic   
            foreach C in [math]N_i[/math] where [math] C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i [/math]
               makeFA([math]q_C, X_1 \ldots X_m, q_1[/math])             
            foreach C,D in [math]N_i[/math] where [math] C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i [/math]
               makeFA([math]q_D, X_1 \ldots X_m, q_C[/math])
               [math] \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} [/math] 
             return
    foreach p in [math]P[/math] where p == [math] a \rightarrow \beta [/math]
       makeFA([math] q_0, \beta, q_1 [/math])

Аппроксимации самоприменимой грамматики

В данном разделе покажем методы апроксимации: [math]\mathrm {RTN}[/math] (recursive transition network) аппроксимацию и [math]\mathrm {MN}[/math] (Mohri and Nederhof's) аппроксимацию — самоприменимой контекстно-свободной грамматики [math] G = \langle N, \Sigma, P, S \rangle[/math] к регулярной грамматике. Для удобства будем считать, что грамматика представлена в НФХ.

Автоматы [math]T_A,T_B[/math] для грамматики [math]A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f [/math]

RTN аппроксимация

Построим, по данной грамматике аппроксимирующий ее конечный автомат.

Конечный автомат для грамматики [math]A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f [/math]
  1. Для каждого нетерминала [math] A[/math] в грамматике, создадим новый конечный автомат [math] T_A[/math], добавим в него два состояния [math] q_A[/math] и [math]q_{A^*}[/math].
  2. Для каждого правила грамматике [math] (A \rightarrow X_1 \ldots X_m ) \in P[/math], введм новые состояния в автомат этого нетерминала [math] q_0^A \ldots q_m^A[/math], а также добавим новые правила перехода в [math] \Delta[/math]: [math] (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \ldots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})[/math].
  3. Таким образом мы построили множество конечных автоматов [math]T[/math] = [math] \{ T_A \mid A \in N\}[/math] для каждого нетерминала [math]A[/math]. Теперь объединим все в один автомат. Объединим все состоянии автоматов из [math]T[/math] в множество [math]Q[/math]. Скопируем все переходы каждого автомата из [math]T[/math] в [math]\Delta[/math]. Далее для каждого перехода вида [math](q,A,p), A\in N[/math], вместо него добавим два новых перехода: [math] (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) [/math].

MN аппроксимация

Построим по данной самоприменимой контекстно-свободной грамматике [math] G [/math] регулярную грамматику [math] G^*[/math].

  1. Для каждого нетерминала [math] A \in N [/math] из [math]G[/math], добавим нетерминалы [math]A[/math] и [math] A^*[/math] в [math] G^* [/math].
  2. Для каждого правила [math] A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \ldots B_m {\alpha}_{m}[/math], где [math] B_1, \ldots, B_m \in N \land {\alpha}_i \in \Sigma^*[/math]. Добавим в [math] G^*[/math] нетерминалы [math] B_1 \ldots B_m , B_1^* \ldots B_m^*[/math] и следуюшие правила: [math]\begin{cases} A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \ldots \\ B^*_m \rightarrow {\alpha}_m A^* \end{cases}[/math].
(Если [math]m = 0 [/math], тогда добавим правило [math] A \rightarrow {\alpha}_0 A^* [/math]).

В итоге [math] G^*[/math]правоконтекстная грамматика, эквивалентная конечному автомату, который задает регулярный язык.

Пример

[math] G = \begin{cases} A \rightarrow \alpha B \alpha \\ B \rightarrow \beta A | \beta \end{cases}\Rightarrow G^* = \begin{cases} A \rightarrow \alpha B \\ A^* \rightarrow B^* | \varepsilon \\ B \rightarrow \beta A | \beta B^* \\ B^* \rightarrow \alpha A^* | \varepsilon \end{cases}[/math]

Исходная грамматика [math] G [/math] генерирует язык: [math] \{(ab)^n a^n \mid n \gt 0\}[/math]. Результирущая грамматика [math] G^*[/math] генирирует регулярный язык: [math] (ab)^+ a^*[/math].

Сравнение двух методов

Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. Привлекателным свойством [math]\mathrm {MN}[/math] аппроксимации по сравнению с [math]\mathrm {RTN}[/math], то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике [math] G[/math], добавляется не более одного нового нетерминала в [math] G^*[/math] и размер результирующий грамматики максимум в [math]2[/math] раза больше, чем размер исходной. Так как для [math]\mathrm {RTN}[/math] апроксимации грамматики [math] G = \langle N, \Sigma, P, S \rangle[/math], количество состаяний апроксимируещего автомата в худшем случаи может составлять [math] O(|N|^2)[/math], что может быть критично для аппроксимации больших грамматик. Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

См. также

Примечания

Источники информации