MCS388 Homework 1 (Spring 2003)
Due: February 19, 2003

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

Answer each of the following questions about the grammar
S > 1  1S  10S  S1

Is this grammar unambiguous? Justify your answer.

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.

Can the grammar generate a binary representation of each
positive odd number? Justify your answer.

Give an unambiguous grammar that generates the same language as the
grammar of exercise 2.2c on page 78.
Course web site: http://www.gac.edu/~max/courses/S2003/MCS388/
Instructor: Max Hailperin <max@gac.edu>