Homework 6

Details

1. 2.1
2. 2.4b
3. 2.4c
4. 2.4e
5. 2.5a
6. This problem is too problematic. It doesn't exist. (Bonus) Prove or disprove that the language generated by the CFG defined as follows is inherently ambiguous.

   S	→	Aa | bB
   A	→	Ba | Aa | a
   B	→	bA | bB | b

   (Hint: To prove it is not inherently ambiguous, find another CFG that describes the same language and show it is not ambiguous. To prove it is inherently ambiguous, argue that there are certain strings that will always have two different parse trees, no matter what grammar is used to generate the language.)