Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA recognizes that language $L$?

share|cite|improve this question
I also read it this way the first time: "it is sufficient..." instead of "is it sufficient" ;-) – dtldarek Mar 13 '12 at 20:05
Sorry for bad punctuation. Edited. – atlantis Mar 13 '12 at 20:06
It is sufficient to draw some PDA, prove that it is equivalent to $G$, and then show that this PDA recognizes $L$. – dtldarek Mar 13 '12 at 20:07
up vote 1 down vote accepted

It will work (if, as dtldarek said, you also prove that the automaton is actually equivalent to the grammar). But it doesn't in general feel like a productive strategy. Of course this can depend a lot on how the language $L$ is given -- but how many tools do you have which you can you can use on automatons, and not as well apply directly to the original grammar?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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