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
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/MCS-388/
Instructor: Max Hailperin <max@gac.edu>