COT 6315/CS 710-R Spring 1998 -- Final Examination

This open-book examination is to take 120 minutes. Answer exactly five of the eight questions presented below. Make sure you answer briefly but clearly. Extraneous incorrect information will cause the score for otherwise correct answers to be lowered.

No aid other than your textbook is allowed on this examination.

Pledge (Must be signed according to UF Honor Code)

On my honor, I have neither given nor received unauthorized aid in doing this assignment.
________________________________ (signature)

Examination Questions

  1. Let L = {<M,a> | M writes character a after being started on an empty tape}.
    Is L decidable?
  2. Let z be a fixed string of length n over alphabet {0,1}. What is the smallest number of states a DFA can have if it accepts the language (0 U 1)*z? Prove your answer.

    (Hint: consider what would happen if there were loops in the state sequence accepting the suffix z of a string.)
  3. Let L be the set of even length strings with the two middle symbols equal.
    Is L regular?
  4. Show that if L is accepted by a PDA, then L is accepted by a PDA in which there are at most two stack symbols.
  5. Consider the language L = {<M> | M halts on some string w within 10 moves}.
    Is L decidable?
  6. Show that the language L = {aibjck | i >= j or i >=k} is a CFL but that its complement is not a CFL.
  7. Why is Rice's theorem only valid for nontrivial language properties?
  8. Show that the Post Correspondence Problem is decidable relative to ATM.
This document is copyright 1998 by Joseph N. Wilson.