[Solved]: Pushdown Automata: CFG to PDA

Problem Detail: 

I have the following grammar for a context-free language:

$G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$

My question is: How to construct a pushdown automaton associated with the above grammar?

Asked By : Highlights Factory

Answered By : Vigneshwaren

The language $L$ accepted by the CFG can be written of the form,

$$ L = \{x^nyz^n | n \gt 0\}$$

You can verify this, by looking at members of $L$

Now there are various definitions of $PDA$ (accept by final state, accept by empty stack), the most simple definition that is suitable for this problem is to user a $PDA$ that accepts through empty stack.

Now the intuitive idea is to push all $x$'s on to the stack, and when you read a $y$, pop the $x$'s in the stack for every $z$ you read afterwards. (So this can be quite easily achieved by a deterministic $PDA$. Verify.)

The transition table $T$ for a $PDA$, with states $Q = \{q_0, q_1,q_2,q_3\}$ and stack symbols $\{X,\$ \}$ is:

$$ \delta (q_0,$,x) = (q_1,$X) $$ $$ \delta (q_1,\epsilon,x) = (q_1,X) $$ $$ \delta (q_1,\epsilon,y) = (q_2,\epsilon) $$ $$ \delta (q_2,X,z) = (q_2,\epsilon) $$ $$ \delta (q_2,$,\epsilon) = (q_3,\epsilon) $$

The automaton transitions to state $q_3$ once an equal number of $x$'s and $z$'s are read

NOTE: My first answer. Kindly bear with errors (technical or LaTex related)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35918