$$begin{gather*} delta(q_0,1,Z) = (q_0,XZ) {}[q_0,Z,q_0] to 1[q_0,X,q_0][q_0,Z,q_0] {}[q_0,Z,q_0] to 1[q_0,X,q_1][q_1,Z,q_0] {}[q_0,Z,q_1] to 1[q_0,X,q_0][q_0,Z,q_1] {}[q_0,Z,q_1] to 1[q_0,X,q_1][q_1,Z,q_1] end{gather*}$$ $$ begin{gather*} delta(q_1,0,Z) = (q_0,Z) {}[q_1,Z,q_0 ] to 0[q_0,Z,q_0] {}[q_1,Z,q_1 ] to 0[q_0,Z,q_1] end{gather*}$$
How do I decide which state makes it into final production, and which one will be excluded ?
Asked By : newprint
Answered By : Ran G.
For a given grammar $G=(V,T,S,P)$, we say that some variable $X in V$ is unreachable if it cannot be reached from $S$, that is, there is no $alpha in (V cup T)^*$ such that $Sto^* alpha$ and $Xin alpha$.
You can find unreachable variables by a straightforward BFS search starting from “$S$”. To complete the answer, let me also note that there are another type of variables, which we call unproductive (or “dead”). Those variables will cause the derivation never to terminate. Formally:
We say that a variable $Xin V$ is unproductive if for any $alpha in (Vcup T)^*$ such that $Xto^*alpha$, $alpha$ has at least one variable, that is, $alpha notin T^*$.
For instance, if $Sto A mid 1$ and $Ato A1$, then $A$ is unproductive—you can never get rid of it. Unproductive variables are also quite easy to find, and can be removed from the grammar (possibly along with some other productions, in which they appear on the right-hand-side.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2503