CSE 105 Assignment 8 WITH REVISED VERSION OF PROBLEM 6
Due: June 4, 1998 at the beginning of class
NO LATE HOMEWORK

Problems:

  • Problem 1:
    Show that if L is accepted by a PDA M by final state (i.e. L=L(M)), then L is accepted by a PDA by empty stack (i.e. there exists a PDA M' such that L=N(M)).

  • Problem 2:
    Chapter 7, 7.1 b,c

  • Problem 3:
    Show that the set of CFLs is Turing-acceptable (recursively enumerable) by showing that every language accepted by a PDA is accepted by a Turing Machine.

    Problem 4:
    Show that the class of Turing-decidable languages is closed under concatenation and Kleene star (*).

    Problem 5:
    Show that the following questions are undecidable:
    * "Given TM M, does M accept all strings?" (the everything problem)
    * "Given TM M, does M accept the empty string?" (the empty string problem)

    Problem 6:
    It turns out that the correct form of this question is in the book! Therefore, please read page 185 for the proof of the following. There is nothing to turn in.

    The book shows that it is Turing-acceptable (r.e.) but not Turing-decidable (recursive) to determine if a TM halts on any string. The language which represents this question is Lne.