Изменения
→MT аппроксимация
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha A B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
<br/>Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. <br/><br/>
Ясно, что язык генерируемый апрокисимируещей граматикой содержит в себе язык генерируемый исходнодй грамматикой. <br/>
Также, привлекателным свойством такой аппроксимации, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в 2 раза больше, чем размер исходной.<br/>
== Источники ==
