# Simple Pushdown Automaton

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.

• What have you tried and where did you get stuck? Hint: start with a PDA for $x^n y^n$. – Raphael Nov 14 '14 at 9:26

• Agree with the solution by Peter Olson. Moreover, we can make it simpler by removing $L \to xBx$. Because $L \to xBx = L \to xLx \to xBx$ – htedsv Nov 14 '14 at 10:57