[Solved]: Eliminating useless productions resulting from PDA to CFG converison

Problem Detail: 

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.

For example, for two transitions, I am getting the following productions

$$\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.

It is not very clear what you wish to achieve. Do you wish to reduce the number of productions to the minimal possible? Do you only wish to avoid productions that are "not helpful" i.e., never appear in any valid derivation?

The first question seems difficult (e.g., This Work shows that it is NP-hard to approximate the length of the smallest grammar within a certain constant factor)

If you talk about the second issue, more things can be done. You should look on methods for converting grammar into a normal form (like Chomsky- or Greibach- normal form), since usually the first step in those conversions is to eliminate any unnecessary productions.

To be more specific, the most easy thing we can do, is to eliminate unreachable variables:

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 $S\to^* \alpha$ and $X\in \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 $X\in V$ is unproductive if for any $\alpha \in (V\cup T)^*$ such that $X\to^*\alpha$, $\alpha$ has at least one variable, that is, $\alpha \notin T^*$.

For instance, if $S\to A \mid 1$ and $A\to 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