Problem Detail: I’m currently learning about PDAs and their power when constructing them from Context-Free Grammars, however I’m still unsure of how to properly construct a CFG, and then a PDA from that CFG. In the book, Formal Languages, Automata, and Complexity, by J. Glenn Brookshear, there are a few exercises requiring I construct a PDA from a given CFG. One of them is $qquad L= {x^n y^m x^n mid n,m geq 0}$. I can construct a PDA for $x^n y^m$, but am unsure of how to finish off the PDA.
Asked By : Delfino
Answered By : Peter Olson
You can create a context free grammar for L thus:
L -> B | xBx | xLx B -> ε | yB
Then you can follow a construction algorithm converting a context free grammar into a pushdown automaton. Here is an example of such a construction (please excuse my lousy graphics): 
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33078 3.2K people like this
