[Solved]: Simple Pushdown Automaton

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

 Download Related Notes/Documents