2 Grammars as a Generating Device

generate $a^nb^nc^n$ grammar from using

1. Ss -> abc | aSQ 
2. bQc -> bbcc
3. cQ -> Qc

This way of doing things is called breadth-first production; computers are better at it than people.

S = N | L, '&', N ;
N = 't' | 'd' | 'h' ;
L = N, ',', L | N ;

Problems

1. Undefined Non-Terminals
2. Unreachable Non-Terminals
3. Non-Productive Rules and Non-Terminals
   1. Suppose X has as its only rule X → aX and suppose X can be reached from the start symbol. Now X will still not contribute anything to the sentences of the language of the grammar, since once X is introduced, there is no way to get rid of it: X is a non-productive non-terminal.
4. loops

These four groups together are called useless non-terminals.

// A demo grammar for grammar cleaning
S ---> AB|DE
A ---> a
B ---> bC
C ---> c
D ---> dF
E ---> e
F ---> fD

We solve this dilemma by first marking all rules and non-terminals as “Don’t know”. We now go through the grammar of demo and for each rule for which we do know that all its right-hand side members are productive, we mark the rule and the non-terminal it defines as “Productive”.