CSE 105 Assignment 3

Due date, July 21, 2003, 8:00 AM.

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. Show that the set of regular expressions over the binary alphabet is a context-free language.
  2. Consider the language ADD in Problem 1 of Assignment 2.
    1. Show that ADD satisfies the conditions of the pumping lemma for context-free languages.
    2. Does this prove that ADD is a context-free language?
    3. Give a context-free grammar for ADD.
  3. Work problem 2.18(a) on page 121 of your textbook.
  4. Work problem 2.27 on page 122 of your textbook.

Back to Course Page