MCS-388 Homework 1 (Spring 2003)
Due: February 19, 2003
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
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
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/MCS-388/
Instructor: Max Hailperin <firstname.lastname@example.org>