University of Nevada, Las Vegas Computer Science 456/656 Spring 1997 Final Exam 6:00 PM, Wednesday, May 7, 1997, TBE B176

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. [4 points each (nothing will be subtracted for a wrong answer).] (a) The intersection of any two context-free languages is context-free.

(b) Given any NFA, there is a DFA that is equivalent.

(c) If a function f : N → N is bounded, that is f(n) = O(1), then f must be recursive. (N is the natural numbers.)

(d) If L_{1} reduces to L_{2} in polynomial time, and if L_{2} is N P, then L_{1} must be N P.

(e) Given any function f : N → N, there exists a recursive function g : N → N such that f(n) = O(g(n)).

2. [15 points] What does it mean to say that L_{1} reduces to L_{2}? (Give a precise definition.)

3. [10 points each] (a) What does it mean to say that machines M_{1} and M_{2} are equivalent?

(b) Draw a minimal DFA that accepts the language given by the regular expression (a + b)^{∗}aabb(a + b)^{∗} (c) The only difference between the definition a CFG and the definition of a general grammar is:

(d) The class of left-linear grammars corresponds to what class of machines?

The class of context-free grammars corresponds to what class of machines? The class of general grammars corresponds to what class of machines?

(e) Given the context free grammar G, whose productions are listed below, give a leftmost derivation of the string dbddssn S → s S → dS S → bLn L → SL L → Λ 4. [15 points] What does it mean to say that a machine M enumerates a language L?

5. [15 points] Give a CFG which generates the language of all regular expressions over {a, b}.

6. [15 points] Suppose f is a partial function from strings to strings. What does it mean to say that a machine M computes f?

7. [35 points] Let L_{d} be the diagonal language, defined as follows:

L_{d} = {⟨M⟩ | ⟨M⟩ ∉ L(M)}

where ⟨M⟩ is the binary encoding of any Turing Machine M. Prove that the diagonal language is not accepted by any Turing machine.

8. [35 points] Use an appropriate pumping lemma to prove that the set of all strings over {0, 1} which have more ones than zeros is not regular.