9
$\begingroup$

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?

|cite|improve this question
$\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
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.