Computer Science 456/656 Fall 1998 Midterm, November 24, 1998

Name: No books, notes, or scratch paper. Use pen or pencil, any color. Use the rest of this page and the backs of the pages for scratch paper. If you need more scratch paper, it will be provided. The entire test is 200 points.

1. True or False. [5 points each] (a) A language is said to be recursive if it has a recursive enumeration.

(b) Any subset of a regular language is a regular language.

(c) Every recursively enumerable language can be generated by a general grammar.

(d) Any partial function that can be computed by any machine can be computed by some Turing Machine.

(e) Every Turing Machine can be emulated by a 2-PDA, defined as a machine just like a PDA, but with two stacks instead of just one.

(f) The complement of every recursive language is recursive.

(g) The complement of every recursively enumerable language is recursively enumerable.

(h) The following problem is decidable: given any general grammar G and any string w, does G generate w?

(i) If L = L(T), where T is an NTM (non-deterministic Turing machine), then L is recursively enumerable.

2. Fill in each blank with one word. [5 points each blank] (a) A language is said to be undecidable if it is not .

(b) A machine M is said to be if for every configuration ξ of M there is at most one configuration of M which follows from ξ in one step.

(c) A is a machine that inputs a string of a language generated by a given grammar and outputs a derivation of that string.

3. Let Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}. Let L be the language over Σ consisting of all strings which are prefixes of the decimal expansion of the well-known real number π. (For example, L includes the strings Λ, 3, 3., 3.1, 3.14, 3.141, …) Prove that L is recursive. [10 points]

4. Informally, describe how a multi-track single tape TM can be emulated by a one-track single tape TM. [15 points]

5. Informally, describe how a multi-tape TM, where each tape has a single track, can be emulated by a multi-track single tape TM. [15 points] 6. Design a parser for the following grammar: [30 points] Hint: your parser may be any of the types that

we studied in class.

1. S → s

2. S → aSSb

3. S → cSdS 7. Use the pumping lemma to prove that the language L = {a^{n}b^{n}a^{n}} is not context-free. [20 points]

3 8. Suppose that L is a language. For each integer n, define P_{n}(L) to be the set of all strings in L whose

lengths are at most n. Suppose that, for each n ≥ 0, P_{n}(L) is recursive. Prove that L is recursive. [20 points] 9. If T is a TM, our textbook uses the notation e(T) to denote the encoding of T. In my lecture on the

board, I used the notation “T ” to mean the same thing as e(T). Suppose that f : N → N is a function which has the following property. If T is a TM whose encoding e(T) has length m, and if w is any string accepted by T, and if |w| = ℓ, then T accepts w in at most f(m + ℓ) steps.

(By the way, such a function f really exists. That fact is easily proved, but I am not asking you for that proof.)

Prove that f is not recursive. (Hint: use the fact that the diagonal language, as defined in class, is not recursive.) [30 points]