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