MCS-388 Homework 1

1. Using the grammar for expr on page 49, show the parse tree for 3-(5-9*2+1) where each of the digits (3, 5, 9, 2, 1) is a digit.

2. Give an unambiguous grammar that generates the same language as the grammar of exercise 2.2.2c on page 51.

3. • Show that all binary strings generated by the following grammar have values divisible by 3. (Hint: Use induction.)

           num  -->  11 | 1001 | num 0 | num num
     

   • Does the grammar generate all binary strings with values divisible by 3?

4. Do exercise 3.3.5, parts h and i only, from pages 125-126.