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.

Course web site:
Instructor: Max Hailperin <>