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

   

     

 

Contributor's Info

Created:
0Comment