Sample Final Exam | Name: _____________________________ |

CSC 8150-001 Theory of Computing

Fall 1999, David Matuszek

- 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.

- Right linear grammar:
- Context free grammar:
- Context sensitive grammar (either form):
- Unrestricted grammar:

- Right linear grammar:
- 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? - 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?

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

- Does the empty string belong to L?

- List all the strings in L of length one:

- List all the strings in L of length two:

- List all the strings in L of length three:

- List all the strings in L of length four:

- Does the empty string belong to L?
- 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.

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

- 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`

`--`

`--`

`--`

`--`

- 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.

- 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).

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

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

- 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.

- Some Turing Machines are
*deciders*and some are*recognizers*.

- What are both deciders and recognizers guaranteed to do?

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

- What are both deciders and recognizers guaranteed to do?
- State the Church-Turing Thesis.

- State the Cook-Levin theorem.

- We gave two alternate definitions of
**NP**. State*one*of them.

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

- There are more fractions than there are integers.

- There are more real numbers than there are integers.

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

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

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

- There are an infinite number of possible Turing Machines.

- There are more languages than there are Turing Machines.

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

- There are more fractions than there are integers.