MCS-388 Homework 2 (Spring 2002)

Due: March 4, 2002

1. Do problem 3.6, parts a-d only, on page 147. Your descriptions should be simple, which may require you to do more than just a literal one-to-one translation of the regular expression notation into English.

2. Sometimes it is easier to specify a regular language using a regular grammar rather than a regular expression or regular definition. A regular grammar is a context free grammar where every production's right hand side has at most one nonterminal, which must be the last symbol.

   Do problem 3.7, part f only, but give your answer as a regular grammar rather than a regular definition. If you want to learn more, you can do the regular definition too.

3. Do problem 4.4 on page 267, parts b-d. Part d calls for constructing a parse tree for the sentence a|b*c, yet that isn't a sentence, because the grammar doesn't allow the terminal c. My suggestion is that you either change the sentence to match the grammar -- by changing the c at the end to an a or b -- or change the grammar to match the sentence, by adding R->c.

4. Do problem 4.5 on page 268.