Sample Final Exam Name: _____________________________

CSC 8150-001 Theory of Computing
Fall 1999, David Matuszek

1. The various grammar types differ only in their productions. Specify the allowable forms of productions for each type of grammar. Use capital letters (A, B, ...) for variables, lowercase letters (a, b, ...) for terminals, Greek letters (α, β, ...) for arbitrary strings, and ε or λ for the empty string.

1. Right linear grammar:

2. Context free grammar:

3. Context sensitive grammar (either form):

4. Unrestricted grammar:

2. In a conventional programming language (such as C), what is the simplest kind of grammar that can be used to recognize the tokens (variables, numbers, keywords, operators) of the language?

3. In a conventional programming language (such as C), what is the simplest kind of grammar that can be used to recognize the statements (`while`, `if`, `switch`, etc.) of the language?

4. Consider the language L described by the regular expression: `(a+b)(ab)*`

1. Does the empty string belong to L?

2. List all the strings in L of length one:

3. List all the strings in L of length two:

4. List all the strings in L of length three:

5. List all the strings in L of length four:

5. Write a context free grammar that produces exactly the same set of strings as the regular expression `(a+b)(ab)*`. (This is the same regular expression as the previous question.) Specify all four parts of the grammar.

6. Using your context free grammar from the previous question, draw a derivation tree for some (one) string of length five.

7. Write a Turing Machine that reads two one-bit numbers and replaces them with their two-bit sum. That is, it replaces `#00#` with `#00#`, `#01#` with `#01#`, `#10#` with `#01#`, and `#11#` with `#10#`, where `#` represents a blank. Assume that the read head is initially positioned over the leftmost bit. This TM is a transducer, not a recognizer, so do not include any `ACCEPT` or `REJECT` states, but do use the `HALT` state. The final position of the read head does not matter. Do no error checking.
 Current state Symbol read Symbol written Direction Next state `HALT` `--` `--` `--` `--`

8. Consider a Turing Machine variant that is just like a standard TM except that it has a constant-length tape (say, 10000 squares). Does this variant have the same power as a standard TM, or is its power reduced to that of one of the other machines we have studied (and if so, which one)? Give a reason for your answer.

9. In class I displayed a flowchart that showed the essential idea of the Halting Problem. Either draw this flowchart or describe in words what the Halting Problem tells us (but not both).

10. How would you go about proving that some problem X is NP-complete? (We did a couple of such proofs in class.)

11. Describe the Hamiltonian Path problem. (Just tell what the problem is, don't discuss how to solve it.)

12. Write an example of a 3SAT formula. It doesn't have to be a meaningful example; I just want to see if you know what 3SAT formulas look like.

13. Some Turing Machines are deciders and some are recognizers.

1. What are both deciders and recognizers guaranteed to do?

2. What is the difference between deciders and recognizers? (And which is which?)

14. State the Church-Turing Thesis.

15. State the Cook-Levin theorem.

16. We gave two alternate definitions of NP. State one of them.

17. True or false. (In all questions, "more" means "a greater number.")

1. There are more fractions than there are integers.

2. There are more real numbers than there are integers.

3. There are more possible Turing Machines than there are possible Deterministic Finite State Automata.

4. Deterministic Turing Machines can recognize more languages than Deterministic Finite State Automata can.

5. Deterministic Turing Machines can recognize some languages that deterministic Finite State Automata cannot recognize.

6. There are an infinite number of possible Turing Machines.

7. There are more languages than there are Turing Machines.

8. Nondeterministic Turing Machines can recognize more languages than deterministic Turing Machines can.