Sample 8510 final exam questions

Some of these are quite difficult; I hope to come up with somewhat easier questions for the final exam. The final exam is comprehensive, but (with one exception) these questions are from the second half of the semester. (You already have plenty of sample questions from the first half of the semester.)

Define each of the following terms:

• The Church-Turing Thesis
• The running time of a nondeterministic Turing machine.
• Reasonable encoding.
• Conjunctive Normal Form.
• Metalanguage.

There are many variations on deterministic Turing machines (DTMs). Suppose you wanted to show that a variant, DTM_v, was at least as fast as a standard Turing machine, DTM_s, on all problems. You get to choose the variant. How could you prove this?

Suppose a deterministic Turing machine has a tape alphabet of k symbols, and a finite tape of only n squares. Can you set a bound on the number of useful states the TM can have? Justify your answer.

True or false: If problem A requires O(f(n)) time (on a deterministic Turing machine), and it can be reduced to problem B in O(f(n)) time, then problem B can be solved in O(f(n)) time.

We wish to prove that two regular expressions are equivalent. This problem

1. Can be solved in polynomial time.
2. Can be solved in exponential time.
3. Is semi-decidable.
4. Cannot be solved (is undecidable in general).
5. None of the above.

Write a context-free grammar for regular expressions over the alphabet {a, b, c, d, e}.