##### Removal Technique

Some times in grammar we have some impurities, which we need to remove.
Types of impurities we have are as follows:
1. Elimination of Epsilon Production:  If ε  is present in the grammar, then we should have at least one ε production, but you can remove others.

Steps with example:

1.   S --> aSb/aAb

A--> ε

• find out all the ε production: Here, A--> ε is ε production.
• find out all the nullable variables: here nullable variable is A
• Write down all the production with and without nullable variables , and remove ε

S --> aSb/ aAb/ ab

• If any variable is not present then remove it from all the production.

S --> aSb/ ab

2.   S-->  ABAC

A-->  aA/ ε

B-->   bB/ε

C-->  c

Solution:

S--> ABAC / BAC / ABC / BC/ AC/ C/ AAC

A-->  aA / a

B-->  bB / b

C-->   c

3.   S -->  AbaC

A-->   BC

B-->  b/  ε

C-->  D/ ε

D-->  d

Solution:

S--> AbaC/ baC / Aba/ ba

A--> C /BC / B / ε

B--> b

C--> D

D--> d

But some time removing ε production can give us unit production, which we   also need to remove. for example in above production C--> D is a unit production.

2. Elimination of unit production:

When you see a unit production, just replace the corresponding variables with its terminal that are present in its production.

examples:

1. S -->  Aa /B

B-->  A / bb

A-->  a / bc / B

Solution:

S --> Aa/ a/ bb/ bc

B--> a / bc / bb

A--> a / bc / bb

Sometime eliminating unit prodction gives you useless symbol or useless     prodction , for example here in the solution B--> a / bc / bb , this is uselss   prdcution beacsue B is not reachable from start symbol S so we need to   remove  it.

3. Eliminating useless production:

Steps:  1. first check whether the variable is reachable from the start symbol.

2. Check if the production contains a useful symbol.

3. Useful Symbols are : Start variable, terminals, and variable which have productions made up of only these two things.

Examples:

1.  S--> AB / a

A--> BC / b

B--> aB/   C

C--> aC / B

Solution :

Useful symbol are {a,b, S,A}

now if you see B and C does not have production which are made of useful            symbol so remove them and remove all the production that contains B and            C

S--> a

A-->b

now you see that A is not reachable from S so remove it also

S--> a

2.  S--> ABC / BaB

A--> aA / BaC / aaa

B--> bBb / a

C--> CA / AC

Solution:

Useful Symbol are: {a,b,A,B,S} but C is useless so remove it and remove all              the  production that conatins C

S--> BaB

A--> aA/ aaa

B--> bBb / a

but A is not reachable fro S so remove it and all its prodction

S--> BaB

B--> bBb / a