2
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ What makes you think that some productions are unnecessary? Of course, this grammar simulates the automaton so it is probably not the smallest you can get, but it may very well be minimal (!= smallest). $\endgroup$
    – Raphael
    Commented Jun 27, 2012 at 12:53

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ Note that both "optimisations" are easily computed. The resulting grammars are often called "reduced". $\endgroup$
    – Raphael
    Commented Oct 2, 2012 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.