Изменения

#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>.<br />(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).В итоге <tex> 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>