Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks about some rules could anyone explain that?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ check wikipedia, and this question. The idea is to generate the word (using the grammar) on the stack, and match it to the input. The trick is to do it in parallel - generate part of the word, check it, generate some more, check it, etc. $\endgroup$– Ran G.Apr 10 '13 at 5:31
-
2$\begingroup$ A video which covers this topic, and is easy to understand: youtube.com/watch?v=MJ9xNavURY8 $\endgroup$– Ran G.Apr 10 '13 at 5:39
Add a comment
|
$\begingroup$
$\endgroup$
The actual rules for this construction of a PDA from a given CFGare given on slide 7 in this presentation. Wikipedia calls these rules "match" and "expand". The context-free rules are simulated on the stack (leftmost variable rewritten) and whenever a terminal is generated it is compared with the next symbol on the input. The PDA needs only a single state $1$.
intitial stack symbol $S$ (the axiom of the grammar)
$(1,\varepsilon ,A,1,\alpha )$ for each rule $A\to \alpha$ (expand)
$(1,a,a,1,\varepsilon )$ for each terminal symbol $a$ (match)
Note however that this PDA will accept "by empty stack", i.e., whenever the stack is empty after the input has been read. Common PDA models accept "by final state", i.e., whenever an accepting state is reached after the input has been read. For this we need another state $2$ for accepting and a new bottom of stack symbol $Z$ to recognize the empty stack and move to the accepting state. We have to start with $SZ$ on the stack now, and since classical models start with a single stacksymbol here we start with $Z_0$ and rewrite in the first step.
$(1,\varepsilon ,Z_0,1,SZ )$ (initialize)
expand and match as before
$(1,\varepsilon ,Z,2,Z )$ (move to accepting state)
The slides you use are from a course by Jeff Ullman it seems. (One of the authors of a famous book on formal languages and automata). He also has prepared an online course on the topic, where I guess he will explain the details himself.
answered Apr 10 '13 at 7:32