Quiz 7                                                                    ROLL NO:____________________

 

CS 311 'Automata & Complexity Theory'                                             Tuesday, June 25, 2002

Time: 10 min.                                                                                    Total marks: 10

      Open Book / Open Notes

 

Convert the following in Greibach Normal Form (show all steps):

S = {c,d}

                                                                                                                                      

 

Possible Solution

 

Step 1: Rewrite the grammar in Chomsky normal form

The grammar is already in Chomsky normal form

Step 2: Relabel the variables A1, A2,, A3

           

            Substituting       S for A1

                                    C for A2

                                    A for A3

                                    B for A4

                Hence,

                        A1 A2 A3

                        A3 d

                        A2 A2 A2 | A4 A3

                        A4 c

 

Step 3: Use Theorems 6.1 and 6.2 to rewrite the grammar into Greibach Normal Form

 

            The production A2 A2 A2 | A4 A3 violates the required conditions

 

            So, this production can also be written as:

 

                        A2 A4 A3 Z | A4 A3

                                Z A2 Z | A2

                       

            Hence, we get the following grammar:

 

                        A1 A2 A3

                        A3 d

                        A2 A4 A3 Z | A4 A3

                                Z A2 Z | A2

                        A4 c

                       

            Now by substituting the variables, we get:

 

                        A1 c A3 Z A3  | c A3 A3

                        A2 c A3 Z | c A3

                        A3 d

                        A4 c

                                Z c A3 Z Z | c A3 Z | c A3

 

                        Which is the required Normal Form.