Стеков автомат по дадена граматика

[micobg]

Как се прави стеков автомат по дадена граматика (контекстно-свободна), такъв, че да разпознава същият език?

[Masterkiller]

В доказателството, че всеки контекстно-свободен език се разпознава от стеков автомат се построява такъв (макар, че не е най-добрия):
Ако има контекствно-свободна граматика: [tex]G=<V, \Sigma, R, S>[/tex]
Автомата ти М има следните свойства:
Множество на състояния: [tex]\left\{p, q\right\}[/tex]
Азбука: [tex]\Sigma[/tex]
Азбука на стека = [tex]V[/tex]
Начално състояние: [tex]p[/tex]
Множество на крайните състояния: [tex]\left\{q\right\}[/tex]
Правила:
1) [tex]((p, \epsilon, \epsilon), (q, S))[/tex] - безусловно преминава от началното състояние p, в крайното q и вкарва началния нетерминален символ на граматиката в стека.
2) Ако имаш правило [tex]A \rightarrow \alpha[/tex], където А е нетерминал и [tex]\alpha \in V*[/tex] (тоест от нетерминал получаваш нула или повече букви - може в тези букви да има и други нетерминали), слагаш правило на стековия автомат [tex]((q, \epsilon, A),(q, \alpha))[/tex]. Това правило прави така, че ако на върха на стека имаш нетерминал, го заменя по правилото в граматиката.
3) За всеки терминал [tex]a \in \Sigma[/tex] поставяш правило [tex]((p, a, a),(q, \epsilon)[/tex] - тоест ако при прочитането на думата, буквата, която четеш, съвпада с буквата от върха на стека, махаш тази буква от стека.

Полученият автомат разпознава граматиката всяка дума от граматиката: [tex]L(G)=L(M)[/tex], но по недетерминиран начин, тъй като не само имаш безусловни преходи, но и за един нетерминал може да има няколко различни правила.

[micobg]

Благодаря много за изчерпателния отговор!