CS 456/656 Assignment 2

Due date: Thursday, February 10, 2005, 11:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
  1. Consider the languages given in Exercise 1.4 on page 84 of your textbook. Write a regular expression for each of those languages. The shorter the regular expression is, the better.
  2. Work Problem 1.36 on page 89 of your textbook.
  3. Work Exercise 2.1 on page 119 of your textbook. Note that the start symbol for this grammar is E, not S.
  4. Work Exercise 2.3 on page 120 of your textbook, odds only. (i.e, (a), (c), etc.) If the answer is "True," then give a derivation or a parse tree.
  5. Work Exercise 2.4 on page 120 of your textbook, odds only. (i.e, (a), (c), etc.) Please make your grammar as simple as you can.

Back to Course Page