Simplifying Grammars

Reducing the number of variables in a grammar

Under certain circumstances, the number of variables in a CFG can be reduced. Consider the variable $B$ in the grammar below:

Since the replacement rules for $B$ do not directly refer to $B$ itself, we can easily substitute its two rules where $B$ appears in the third rule for $A$:

This grammar now has only one variable. This type of back substitution is possible when a rule is not directly recursive. A variable is directly recursive if it appears anywhere in any of its right-hand side rules.

When we convert PDAs to CFGs, some rules generated by the conversion procedure don’t make sense. For example, a variable other than the start variable might never appear on the right-hand side of any rule. Such a variable ...