University of Nevada, Las Vegas Computer Science 456/656 Spring 1998 Final Exam 6:00 PM, Wednesday, May 13, 1998, TBE B178

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] (a) The intersection of any two context-free languages is context-free.

(b) Every subset of a regular set of integers is regular.

(c) For any finite automaton, there is a unique minimal deterministic finite automaton equivalent to it.

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

(e) Every recursively enumerable language is generated by some general grammar.

2. [15 points] Consider the context-free grammar with start symbol S and productions as follows: S → s S → aAn S → bB A → Λ A → SA B → SS Write a leftmost derivation of the string asbssbasnsn 3. [10 points each]

(a) Write a regular expression for the language of all strings over {a, b} which do not contain the substring aab.

(b) We write e(T) to be the binary encoding for any Turing machine, T. What is the diagonal language?

(c) Let Σ = {0, 1} be the binary alphabet. Each string over Σ represents a non-negative integer using binary numeration, where leading zeros don’t count (for example, 0011, 011, 11 all represent 3) and the empty string represents 0. Draw a picture of the minimal DFA which accepts the language L ⊆ Σ^{⋆} of all strings which represent multiples of 3.

(d) If a 2-tape Turing machine takes f(n)-time to work a problem, approximately how much time would a regular TM take to work the same problem? (Express in big O notation.)

(e) What does it mean to say that a context free grammar is ambiguous?

4. [15 points] Suppose that Σ and Γ are alphabets, and that f : Σ^{∗} → Γ^{∗} is a function. What does it mean to say that f is in class P-time? (Be explicit: if you use the word “polynomial,” you must define that word.)

5. [15 points] Give an example of a language which is the class N P-time but not in the class P-time.

6. [15 points] Give the definitions of PDA and DPDA, stressing the difference between a DPDA and a PDA.

7. [35 points] Let Σ = {0, 1}, the binary alphabet. Let L be the set of all strings w over Σ where the number of 0’s in w is the square of the number of 1’s in w. (For example, Λ, 10, 01, 010001, 100100, 011000001000, are all in L) Use the pumping lemma to prove that L is not a context-free language.

8. [35 points] During one lecture, I proved that if T is a Turing machine that enumerates a language L in canonical order, then L is decidable. Give that proof, or a different correct proof if you prefer. Hint: If you write less than a fourth of a page, you are probably missing something.