COT 6315/CM 710-R Summer 2000 - Final Examination

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

Final Examination

This examination is a closed book examination. It is prepared with an expected completion time of 75 minutes. It is to be taken in a period of time no longer than 75 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 6 of the following 8 questions. Clearly note which two questions you do NOT want graded.

I am NOT answering the following two questions: _____ and _____.

If A mapping reduces to B and B is a regular language, does that imply that A is a regular language? Why or why not?
Let AMBIG_CFG = { <G > | G is an ambiguous CFG}. Show that AMBIG is undecidable by using the following reduction from PCP. Given an instance P = { [t₁/b₁] , [t₂/b₂] , ... [t_k/b_k] }, of the PCP, construct a CFG G with the rules
```
S -> T | B
T -> t₁Ta₁ | ... t_kTa_k | t₁a₁ ... | t_ka_k
B -> b₁Ba₁ | ... b_kBa_k | b₁a₁ ... | b_ka_k,
```
where a₁, ... a_k are unique symbols disjoint from the symbols in the strings of P. Explain how this reduction works.
Is it decidable whether or not a Turing machine M will read the first blank tape symbol on input w? Demonstrate the correctness of your answer.
Suppose we use a formal representation of Turing machines as binary numbers. Say that M is a minimal Turing machine if there is no Turing machine equivalent to M that is represented by a smaller number. Describe an upper bound on any finite set of minimal representations of Turing machines that can be enumerated, that is, tell a Machine whose description we cannot exceed in such a set.
Show that the language C = { x#y | x, y are in {0,1}* and x != y } is a CFL. (Read the symbol != as ``is not equal to.'')
Hint: Use a PDA (nondeterministic) to check that the condition holds.
Let L = { x<y | x and y are binary representations of numbers. Is L regular? Demonstrate the correctness of your answer.
Show that there is a property of languages that is not satisfied by any Turing-recognizable language.
Explain how we could uniquely represent a Turing machine with a string of 0s.