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