Homework 11 CS 301 Languages and Automata Fall 2010
Due Date:
10:30 am on Tuesday, Nov 30, in class or Min Shen (TA)'s mailbox (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
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. Problem 4.22
  2. Exercise 5.1
  3. Exercise 5.2
  4. Exercise 5.3
  5. A and B are Turing-recognizable languages.
    1. Is (A intersection B) Turing-recognizable? Justify. If yes, give a TM that recognizes the language.
    2. Is (A union B) Turing-recognizable? Justify. If yes, give a TM that recognizes the language.
  6. A is a Turing-recognizable language. A-comp is its complement such that A-comp is not Turing-recognizable.
    Consider the language A' = {0w | w in A} UNION {1w | w not in A}
    Is A' Turing-decidable, Turing-recognizable, or not even Turing-recognizable? Justify your answer.
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. Exercise 5.5 (No. Dropped from syllabus on 11/23)
  2. Exercise 5.7 (No. Dropped from syllabus on 11/23)
  3. Read the following documents linked from the class web page (and flagged with the NEW symbol).
    1. The Game of Life
    2. Computability
    3. Chomsky hierarchy of grammars
    4. Tiling problem, Halting problem, simplified
    5. Examples of undecidable problems (Wapedia) or from Wikipedia