177
правок
Изменения
м
→RTN аппроксимация
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| mid A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.
===MN аппроксимация ===
