MCS-388 Homework 1 (Spring 2002)

Due: February 18, 2002

1. Using the grammar for expr on page 32, show the parse tree for 2*(4-6*8), where each of the digits (2, 4, 6, 8) is a digit.
2. Do problem 2.5 on page 79.
3. For the grammar of problem 2.2b on page 78, prove the following:
   1. The excess of a's over operators (+'s and -'s) in any S (i.e., any string derivable from S) is 1.
   2. The excess of a's over operators in any proper prefix of an S is less than 1. (If there are more operators than a's, the excess is negative. A proper prefix means a prefix that is not empty and is not the entire string. The restriction to non-empty prefixes isn't needed here, since the excess in an empty prefix is of course 0.)
   3. The grammar is unambiguous.