CSC 456/656 Assignment 3

Due date: Tuesday, March 9, 2004, 11:30 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. Consider the language ADD in Problem 1 above.
    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 Exercise 2.4 on page 120 of your textbook.
  4. Work Exercise 2.3 on page 120 of your textbook.
  5. Work Exercise 2.6(a) on page 120 of your textbook. Your grammar need not be unambiguous.
  6. Work Exercise 2.7 on page 120 of your textbook, but only the part that refers to 2.6(a). Work this exercise twice, once by the bottom-up method, and once by the top-down method. In both cases, your PDA should be designed to be consistent with your answer to Exercise 2.6(a).
  7. Problem 2.21 seems very difficult, but has substantial practical importance for compilers, and is closely related to a problem that I will put on the exam on March 23. Think about it and try to work it, but do not hand it in.

Back to Course Page