Homework 8 CS 301 Languages and Automata Fall 2010
Due Date:
10:45am on Thurs, Oct 28, in class (strongly recommended)
12:00 noon on Fri, Oct 29, in recitation section SES 238 (hard deadline)

Please state any assumptions you make very clearly. Answer the questions in your own words. You must do the homework individually.

Link up to the course web page

It has been brought to my attention after the TA's grading the homeworks that some of you are using different editions of the book (or perhaps the "same" 2nd edtion has different exercises / problems). If you think that is the case, you should copy the question from the book before answering it. That will let the TA know what he is grading. But please, please, try to get the correct 2nd edition of the book, that will simplify the workload on the TA, so he does not have to grade unique problems for each student!
Link to i301 web page where Min posts copies of the homework questions for the benefit of those students who have a different version of the textbook

Solve the following questions and turn in the answers.
  1. Exercise 2.16
  2. Suppose L is context-free and R is a regular language.
    1. Is L - R necessarily context-free?
    2. Is R - L necessarily context-free?
  3. Problem 2.23
  4. Problem 2.24
  5. Problem 2.27
  6. Problem 2.30 (a),(d)
  7. Problem 2.31
  8. Problem 2.32
The following are self-study/ practice only, do not turn in solutions to these. If the answers are given in the book, then check your answers. If the solution is not clear, you can ask the TA in the recitation section.
  1. Problem 2.18
  2. Problem 2.21
  3. Problem 2.22
  4. Problem 2.30 (b), (c)
  5. Problem 2.33
  6. A non-deterministic PDA is more powerful than a detrministic PDA, i.e., there are some CFL that cannot be recognized by a determinisitc PDA. (This is unlike the case for Regular Languages, for which a DFA and NFA had the same power.) Explain in words why the non-deterministic PDA is more powerful than a determinisitc PDA.
    It might help to try to build a determinisitc PDA for a language such as in Example 2.16 or 2.18.