MCS-388 Homework 1 (Spring 2003)

Due: February 19, 2003

1. Using the grammar for expr on page 32, show the parse tree for 7-(3-5*4+2), where each of the digits (7,3,5,4,2) is a digit.
2. Answer each of the following questions about the grammar

   S -> 1 | 1S | 10S | S1
   

   1. Is this grammar unambiguous? Justify your answer.
   2. Prove by induction on the number of nodes in a parse tree that any string generated by the grammar is the binary representations of an odd number.
   3. Can the grammar generate a binary representation of each positive odd number? Justify your answer.
3. Give an unambiguous grammar that generates the same language as the grammar of exercise 2.2c on page 78.