In a grammar a grammar symbol X is useless if X can never ap

In a grammar, a grammar symbol X is useless if X can never appear in a derivation of a string. (a) Write an algorithm for eliminating all productions containing useless symbols from a given grammar. (b) Apply your algorithm to the following grammar: :: = 0 | | :: = :: = 1 : = 2 where is the start symbol.

Solution

Algorithm:

Step1:Identify Non generating symbols unreachable symbols.

Set of non generating symbols=V-Set of generating symbols

Step 2:

Identify unreachable Symbols and remove them

Unreachable symbols=(V U T)- Reachable symbols from start symbols

V={S,A,B,C}

Non generating symbol={S A B C}-{S B C}

={A}

Removing A from the production.

S-->0|C

B-->1

C-->2

Identify the non reachable symbol

Non Reachable symbol =(V U T)-reachable symbols

={S B C 0 1 2}- {S C 0 2}

={B 1}

S-->0|C

C-->2