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.

  • $\begingroup$ What have you tried and where did you get stuck? Hint: start with a PDA for $x^n y^n$. $\endgroup$ – 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):

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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