Викиконспекты - Вклад участника [ru]

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

2014-01-19T17:29:39Z

Danek g30: /* Аппроксимации самоприменимой грамматики */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободно-контекстной грамматики <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|left|Конечный автомат для грамматики
<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 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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>

== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:25:24Z

Danek g30: /* Источники */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободно-контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>

== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:24:10Z

Danek g30: /* Апроксимации самоприменимой грамматики */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободно-контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>

== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:20:54Z

Danek g30: /* Идея алгоритма */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:16:22Z

Danek g30: /* Идея алгоритма */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:15:35Z

Danek g30: /* Идея алгоритма */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:14:37Z

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

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)

== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:10:26Z

Danek g30: /* Источники */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21&lpg=PA21&dq=prove+that+grammars+that+are+not+self-embedding+generate+regular+languages.&source=bl&ots=3gFnA7ig-l&sig=Ub9f_BJKv_jdiO7mWRvkYJVamDE&hl=ru&sa=X&ei=qQfcUoy9Nubb4QSI4YGQDg&redir_esc=y#v=onepage&q=prove%20that%20grammars%20that%20are%20not%20self-embedding%20generate%20regular%20languages.&f=false Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T17:06:41Z

Danek g30: /* MT апраксимация */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
== Источники ==
* [http://www.mpi.nl/world/materials/publications/levelt/Levelt_Formal_Grammars_Vol1_1974.pdf Формальное доказательство экивалентости кс не самоприменимых кс языков и регулярных]
* [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 Разобрано много примеров апроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной апроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

2014-01-19T16:50:26Z

Danek g30: /* MT апраксимация */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>

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

2014-01-19T16:29:25Z

Danek g30: /* MT апраксимация */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>.
(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).

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

2014-01-19T16:24:15Z

Danek g30: /* Апроксимации самоприменимой грамматики */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

===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>.

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

2014-01-19T15:23:29Z

Danek g30: /* Апроксимации самоприменимой грамматики */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <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|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>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>.

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

2014-01-19T15:12:16Z

Danek g30: /* RTN апрксимация */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''', если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''', если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <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> // пришли в лист дерева разбора
<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''' // рекурсивный нетерминал rihgt или self
'''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>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].

=== RTN апраксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим два состояния в <tex> T_A</tex>: <tex>q_A,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>.
[[Файл:RTN_Automat1.png|300px|thumb|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </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>.

Файл:RTN Automat1.png

2014-01-19T15:09:31Z

Danek g30:

2013-01-13T17:48:01Z

Danek g30: загружена новая версия «Файл:Brooks 2.png»

2012-12-29T14:03:50Z

Danek g30: /* Вспомогательная Лемма */

== Вспомогательная Лемма ==
{{Лемма
|statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориентированный граф и <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то <tex>\chi(G) \le \Delta(G)</tex>.
|proof=
[[Файл:Brooks_1.png‎|200px|thumb|]]
Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_n,</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. На <tex> i</tex>ом шаге покраски, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей, следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \le \Delta(G)</tex>.

}}

== Теорема ==
{{Теорема
|about= Брукса
|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, тогда <tex>\chi(G) \le \Delta(G)</tex>, где <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>

|proof=
#Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>
#Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>
#Если <tex> \Delta = 2</tex>, то:
## <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>
##<tex> G</tex> нечетный цикл
Поэтому мы будем считать до конца доказательства, что <tex> \Delta(G) \ge 3</tex>.
Если в <tex>G</tex> существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то по выше доказанной лемме <tex> \chi(G) \le \Delta(G)</tex>. То есть осталось рассмотреть случай, когда <tex>G</tex> {{---}} регулярный граф степени <tex>\Delta</tex>.

#Если <tex>G</tex> не является двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex>, где v {{---}} точка сочленения. Пусть <tex>G_1,G_2</tex> две компоненты связности полученный при удалении вершины <tex>v</tex>.Тогда, по выше доказанной лемме <tex>G_1,G_2</tex> можно правильно раскрасить в неболее чем <tex>\Delta</tex> цветов.Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в неболее чем <tex>\Delta</tex> цветов.
#Если в графе <tex> G</tex> <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность .Пусть <tex>G_1,G_2</tex> два подграфа <tex> G:G_1 \cap G_2 = \{v,u\} \land G_1 \cup G_2 = G</tex>. Рассмотрим два случая:
## Если в одном из подграфов <tex> G_1,G_2</tex> <tex> deg\ u < \Delta - 2 </tex> или <tex> deg\ v < \Delta - 2 </tex> то, подграфы <tex>G_1,G_2</tex> можно правильно раскрасить в неболее чем <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.А из этого следует что, граф <tex>G</tex> тоже можно правильно раскрасить в неболее чем <tex>\Delta</tex> цветов.
## Если степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex> например в подграфе <tex>G_1</tex>:
##* <tex> G_1,G_2 </tex> можно правильно раскрасить в неболее чем <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.
##* <tex>\exists p \in G_2: pu \in E \land pv \in E </tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где <tex>deg\ u = deg\ v = 1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были одного цвета.Следовательно,можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
##*<tex>\exists u_1,v_1 \in G_2: uu_1 \in E \land vv_1 \in E \land u_1 \neq v_1 </tex>, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>.Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин <tex> v,u</tex>.Из чего, прямым образом вытекает, что граф <tex> G</tex> можно правильно раскрасить в не более чем не более чем <tex>\Delta </tex> цветов.
#Если вышеописанные случаи не подходят, тогда рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случаи <tex>G = K_n</tex>.Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм [[Обхода в ширину| обхода в ширину]] из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2},</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs.Теперь пусть <tex> v_{n-1} = v</tex>,и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке начиная с <tex>v_{n-2}</tex> в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета.Заметим, что так всегда можно сделать, поскольку на <tex> i</tex>ом шаге покраски,где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей, следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов.Вершину <tex>w</tex>,мы тоже сможем правильно раскрасить в не более чем один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в не более чем не более чем <tex>\Delta</tex> цветов.
}}

== Источники ==

* [http://myweb.facstaff.wwu.edu/sarkara/brooks.pdf Доказательство на английском]
* [http://en.wikipedia.org/wiki/Brooks'_theorem Теорема Брукса на вики]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]