177
правок
Изменения
→MN аппроксимация
Построим по данной самоприменимой контекстно-свободной грамматике <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} \ldots B_m {\alpha}_{m}</tex>, где <tex> B_1, \ldots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \ldots B_m , B_1^* \ldots B_m^*</tex> и следуюшие правила: <tex> \begin{cases} A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \ldots \\ B^*_m \rightarrow {\alpha}_m A^* \end{cases}</tex>.
:(Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
