COT 6315/CM 710-R Formal Languages and Computation Theory (Summer 2000)

Examination 3

This examination is a closed book examination. It is prepared with an expected completion time of 50 minutes. It is to be taken in a period of time no longer than 65 minutes.
On my honor, I have neither given nor received unauthorized aid in completing this examination: ____________________________________. (Sign your name if you agree and wish to receive a grade for this examination.)

NOTE: Complete exactly 5 of the following 6 questions. Clearly note which question you do NOT want graded.

I am NOT answering the following question: _______.

  1. Show that if language A is Turing recognizable but not decidable then the intersection of A with an arbitrary regular language R is not decidable.

  2. Give an implementation-level description of a machine that will accept if and only if its input w is a palindrome, that is, if w = wR.

  3. Let L = { <M> | M is a Turing Machine that accepts some input within its first five moves}. Demonstrate whether or not L is a decidable language.

  4. Show that every undecidable language has a decidable subset.

  5. Suppose M1 and M2 are Turing Machine recognizers for languages L1 and L2 respectively. Show how to directly construct a deterministic recognizer for the concatenation of L1 and L2. Note: this is not trivial because M1 may not halt on inputs that are not in L1.

  6. Prove that the set of languages over alphabet { 0 } is uncountable.

This document is copyright 2000 by Joseph N. Wilson.