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$\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
$\begingroup$
$\endgroup$
The actual rules for this construction are given on slide 7 in this presentation. Wikipedia calls these rules "match" and "expand".
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
