Class Work 11: Chomsky Normal Form for Context Free Grammars

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Grading Notes:

• Submit one answer per group.
• Make sure that the answer is legible.
• Include the full names of all group members on your submitted work (so all get credit).

1. Is the following grammar ambigious? Why or why not?

   S → ASB | ε
   A → aSS | a | ε
   B → SbS | A | bb

2. Convert the above grammar to one in Chomsky Normal Form.