Blog: cs402 Assingment No. 5 Solution

Question-1:                                                                                              Marks [5+8]
Sà XYZ
Xà aX | bX | ^
Yà aY | bY | ^
Zà aZ | ^


a. Remove all NULL productions from the given grammar.                  

b. Remove all UNIT productions from the grammar obtained in part (a).                   

Ansewr-1(a)

Sà XYZ
Xà aX | bX | ^
Yà aY | bY | ^
Zà aZ | ^

1. Xà^ ,  Yà^ ,  Zà^   are Null Productions whereas SàXYZ    is Nullable Prouction

Removing bNull Productions we get

Xà aX | a |  bX | b
Yà aY | a  | bY | b
Zà aZ | a
           
     Replacing Nullable Productions we get

     Sà XYZ  | XY | YZ | XZ | X | Y | Z

Ansewr-1(b)

Unit Productions received after removing Null Productions are

Sà X
Sà Y
Sà Z

Removing Unit Productions we get

Sà X  gives  Sà a                    (using  Xà a)
Sà X  gives  Sà b                    (using  Xà b)
Sà Y  gives  Sà a                    (using  Yà a)
Sà Y  gives  Sà b                    (using  Yà b)
Sà Z  gives  Sà a                    (using   Zà a)

Thus the new CFG will be

Sà XYZ  | XY | YZ | XZ | a | b
Xà aX | a |  bX | b
Yà aY | a  | bY | b
Zà aZ | a
           
Question 2:
Sà mno | mA | nB | oC
Aà mX | ^
Bà nY | ^
Cà oZ | ^
Xà mn | m
Yà no | n
Zà om | o

Draw the total language tree for above CFG.                                            Marks [7]
Answer-2