University of Nevada, Las Vegas Computer Science 456/656 Spring 1999 Final Exam 6:00 PM, Wednesday, May 12, 1999, 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 270 points.

1. True or False. [5 points each] (a) The intersection of any context-free language with any regular language is context-free.

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

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

(d) Every language which is generated by some general grammar is recursive.

2. For each language given, write “R” if the language is recursive, write “RE not R” if the language is recursively enumerable but not recursive, and write “not RE” if the language is not recursively enumerable. [5 points each]

(a) The language consisting of all Pascal programs p such that p halts if given p as its input file.

(b) The language of all encodings of Turing Machines which fail to halt for at least one possible input string.

(c) The 0-1 Traveling Salesman Problem.

3. [10 points] Draw a minimal DFA which accepts the language L over the binary alphabet Σ = {0, 1} consisting of all binary numerals for all positive integers that are divisible by 3.

4. [15 points] Consider the context-free grammar with start symbol S and productions as follows: S → s S → bLn S → iSSt L → Λ L → LS Write a leftmost derivation of the string ibiisstbntsnst 5. [10 points each]

(a) What is the Church-Turing Thesis, and why is it important?

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

(c) Why are we interested in the diagonal language?

6. (a) [20 points] Prove that addition is primitive recursive.

(b) [20 points] Prove that multiplication is primitive recursive. You may use the fact that addition is primitive recursive.

7. (a) [20 points] What is a PDA? Give a precise definition, with all details. 5 (b) [10 points] What is another name for the class of languages which are accepted by PDA’s?

(c) [20 points] Referring the definition you just wrote in (??) define the language accepted by a PDA.

8. (a) [20 points] Give a definition of the language class P-TIME. (b) [20 points] Give a definition of the language class N P-TIME.

9. Let Σ = {0, 1}, the binary alphabet. We say a string w over Σ is fair if w has the same number of 0’s as 1’s. Let Lfair be the set of fair strings over Σ.

(a) [20 points] Give an unambiguous context-free grammar for Lfair. (Partial credit for an ambiguous context-free grammar for Lfair).

(b) [30 points] Use the pumping lemma to prove that Lfair is not regular.