Elimination of Unit production from context free grammar
A Unit production is like below :
S -> BWe will apply below steps to remove Unit production:
- Write production without Unit production
- Check what we are missing because of Step 1
We will understand this using one example:
Given grammar is : S -> Aa/B/c B -> A/bb A -> a/bc/B Solution: Now we will apply step 1: S -> Aa/c B -> bb A -> a/bc Now check what we are missing after applying Step 1: First : S -> B -> bb And : S -> B -> A -> a And : S -> B -> A -> bc So add these in the prodcution list of "S" S -> Aa/c/bb/a/bc B -> bb A -> a/bc Second : B -> A -> a And : B -> A -> bc So add this in the prodcution list of "B" S -> Aa/c/bb/a/bc B -> bb/a/bc A -> a/bc Third: A-> B -> bb So add this in the prodcution list of "A" S -> Aa/c/bb/a/bc B -> bb/a/bc A -> a/bc/bb
We also see one more example with 1 variation:
S -> AC A -> a C -> B/d B -> D D -> E E -> b Solution: Now apply step 1: S -> AC A -> a C -> b Now check what are we missing after applying Step 1: For C: C -> B -> D -> E -> b So add this in the production of "C" S -> AC A -> a C -> d/b For B: B -> D -> E -> b So add this in the production of "B" S -> AC A -> a C -> d/b B -> b Similarily for D and E also add: S -> AC A -> a C -> d/b B -> b D -> b E -> b But if we see that B -> b, D -> b and E -> b productions are useless as they can't be reached, Remove them: S -> AC A -> a C -> d/bNext we will learn about removing useless symbols