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$?
Proving that a grammar generates a language
1
$\begingroup$
computer-science
automata
formal-languages
context-free-grammar
-
0It is sufficient to draw some PDA, **prove** that it is equivalent to $G$, and then show that this PDA recognizes $L$. – 2012-03-13
1 Answers
1
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?