# 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

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):

• This is a good idea in this case, since constructing the PDA directly is tedious. – Rick Decker Nov 13 '14 at 19:42
• Please consider not to encourage undesirable posting behaviour. – Raphael Nov 14 '14 at 9:27
• 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