Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 307

1. Remove unit production S → A
   l while, S ⇒ A and A derives terminal then we say that S generates that terminal.
   Or, S ⇒ A ⇒ a, so add production S → a.
   l while, S ⇒ A ⇒ B and B derives terminals then certainly S generates that terminal.
   Or, S ⇒ A ⇒ B ⇒ b, so add production S → b.


2. Remove unit production A → B
   l while, A ⇒ B and B derives terminals then we say that A generates that terminal.
   Or, A ⇒ B ⇒ b, so add production A ⇒ b.
   l while, A ⇒ B ⇒ S and S derives terminal then we say that A generate that terminal.
   Or, A ⇒ B ⇒ S ⇒ b b, so add production A → b b.


3. Remove unit production B → S
   l while, B ⇒ S and S derives terminal then we say that B generates that that terminal.
   Or, B ⇒ S ⇒ b b, so add production B → b b.
   l while, B ⇒ S ⇒ A and A derives the terminal then we say that B generates that
   terminal.
   Or, B ⇒ S ⇒ A ⇒ a, so add production B → a.
   Hence the grammar becomes
   S → a | b | b b
   A → b | b b | a
   B → b b | a | b
   We further find that symbols A and B are not reachable so they are useless symbols (all
   production derived from A and from B are useless productions) hence remove from the gram-
   mar.
   Therefore, after simplification we obtain the new grammar which is free from all unit
   productions, i.e.,
   S → a | b | b b


4. Remove all useless symbols

There is another approach to eliminate the useless symbols. We may start to search the useful
symbols. The useful symbols are reachable symbols and active non terminals.

Useful Symbol

A symbol X is useful if it occurs in the derivation of terminals from starting symbol S, i.e.

S ⇒N α X β ⇒N x (∈ VT*) for some α and β

[or, S ⇒^1 x ∈ (VT)* then S → x is the useful production]

Active non terminal

Symbol A is active non terminal if it generates the terminal string i.e.

A ⇒N x(∈ VT)*

Algorithm
Assume a grammar G = (VN, VT, S, P) then we find active non terminals as
follows: