Simplified Form of CFG | Sahithyan's Notes

Simplification removes unnecessary productions while preserving the language.

Λ-Productions

Aka. null productions. Allow non-terminals to derive the empty string. Null productions are removed by adding alternative productions. All combinations of nullable symbols must be considered to preserve language.

Removal of null productions

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$ $A \to α$ in $P$ $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.

Unit Productions

Rules of the form $A \Rightarrow^* B$ where $A,B$ are non-terminals.

Does not add new structure to derivations. Can be removed by substitution.

Removal of unit productions

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$ $A \in V$ :
- Find all non-terminals derivable from $A$ (set of $A^*$ )
- For each $B \in A^*$ $B \in A^{*}$ :
  - For each $B \rightarrow \alpha \in P$ , add $A \rightarrow \alpha$ to $P_1$
Delete all unit productions from $P_1$