MCS388 Homework 1 (Spring 2005)
Due: February 15, 2005

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

Answer each of the following questions about the grammar
S > S a S b S  epsilon
where epsilon
represents the empty string:

Is this grammar ambiguous? Justify your answer.

Prove by induction on the number of nodes in a parse tree that any
string generated by the grammar has an equal number of a's and b's.

Can the grammar generate all strings of a's and b's that have an equal
number of a's and b's? Justify your answer.

Consider the grammars of exercises 2.1 and 2.2b on page 78. For each
of these two grammars, answer the following two questions and justify
your answers. Is the grammar suitable for predictive parsing? Is it
ambiguous?
Course web site: http://www.gac.edu/~max/courses/S2005/MCS388/
Instructor: Max Hailperin <max@gac.edu>