Изменения

#Для каждого правила <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>). 

<br/>Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n \mid n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. <br/><br/>

Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. <br/> Привлекателным свойством MN аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик.<br/>