Simplified Form of CFG

Simplification removes unnecessary productions while preserving the language.

Removal of Λ-Productions

Removed by adding alternative productions. All combinations of nullable symbols must be considered to preserve language.

For a given CFG $G=(V, \Sigma, S, P)$, an equivalent CFG $G_1=(V,\Sigma,S,P_1)$ (with no null-productions) can be derived using the following steps:

• Initialize $P_1 = P$
• Find all nullable non-terminals ($\subseteq V$) of $G$ using FindNull algorithm.
• For each $A\rightarrow \alpha$ in $P$:
  • Add all productions that can be obtained by deleting one or more occurences of nullable non-terminals in $\alpha$, to $P_1$
• Remove $\Lambda$-productions and $A\rightarrow A$ productions from $P_1$

Ambiguity is preserved after the elimination of null productions. May increase the number of productions significantly.

Removal of Unit Productions

Removed by substitution. For a given CFG $G=(V, \Sigma, S, P)$, an equivalent CFG $G_1=(V,\Sigma,S,P_1)$ (with no unit-productions) can be derived using the following steps:

• Initialize $P_1=P$
• For each $A \in V$:
  • Find all non-terminals derivable from $A$ (set of $A^*$)
  • For each $B \in A^*$:
    • For each $B \rightarrow \alpha \in P$, add $A \rightarrow \alpha$ to $P_1$
• Delete all unit productions from $P_1$