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
