50
правок
Изменения
→Апроксимации самоприменимой грамматики
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|Конечный автомат для грамматики
===MT апраксимация аппроксимация ===
Построим, по данной самоприменимой кс грамматике <tex> G </tex>, регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
\\ 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 Формальное доказательство, что кс не самоприменимая грамматика генерирует регулярный язык]
