CSE 105 Assignment 2

Due date, July 14, 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. Work this somewhat simplified version of problem 1.36 on page 89 of your textbook:
    Let Sigma = {1,+,=}, and let ADD = {1n+1m=1n+m}. Show that ADD is not a regular language.
  2. Work Exercise 2.3 on page 120 of your textbook, but do not turn it in.
  3. Work Exercise 2.4(b,d,e,f) on page 120 of your textbook.
    Draw PDA's which accept the languages given in (d) and (e).
  4. Work Exercise 2.9 on page 121 of your textbook.
  5. Work Exercise 2.14 on page 121 of your textbook.
  6. Work Exercise 2.17 on page 121 of your textbook, but do not turn it in. Hint: use the theorem that a language is context-free if and only if it is accepted by some PDA.
  7. Work Exercise 2.26 on page 122 of your textbook.

Back to Course Page