Context Free Grammar Useless Productions

Question

I am learning about context-free grammar simplification by the process of removing useless production rules because they are either unreachable or never terminate and I began to wonder why the useless production rules ever existed.

If a grammar has useless production rules, does that not make it an invalid grammar? I feel like by removing production rules you are removing a piece of the language it was "supposed" to have generated if the production rule was not "useless".

In the example grammar below, the production rule "C" is useless because it never terminates and can be eliminated, but if it wasn't useless the language may have strings with the symbol c.

S -> aS | b | C

C -> cC

So, I guess my main question is why is it possible to have useless productions (other than for the sake of example) in a grammar and why do we eliminate the useless production rules as opposed to fixing them so they are not useless?

Answer 1

You are confusing syntax and semantics.

When you say "If a grammar has useless production rules, does that not make it an invalid grammar?" The answer is no. Because, "useless" refers to the semantics of the grammar whereas "invalid" refers to the syntax.

The syntax of a CFG $(S,\Sigma,\Gamma,R)$ is given as:

• $\Sigma$ a set of terminal symbols
• $\Gamma$ a set of non terminal symbols (with $\Sigma\cap\Gamma=\emptyset$)
• $S\in\Gamma$ a starting non terminal symbols,
• $R$ a set of rules of the form $N\to \alpha$ where $N\in\Gamma$ is non terminal and $\alpha\in (\Sigma\cup\Gamma)^*$ is a string of terminal and non terminal symbols.

Every grammar that are of this form are valid. They have the good syntax thus they are CFG.

Once you have defined the syntax of the CFG you can define the semantics. which is that it accept the set of words $w\in\Sigma^*$ for which there is a derivation.

When we say that we can remove the "useless" rules it mean that the obtained grammar is semantically equivalent to the first grammar (i.e. it accept exactly the same words). It absolutely does not change the language!!

However if you "fix" the "useless" rules you can a grammar which is not semantically equivalent to the initial grammar. You obtain two totally different object.

In short, it's ok to do operation preserving the semantics. However any operation changing the semantics give you a different object, thus you don't know what meaning to associate to it.