University of Nevada, Las Vegas Computer Science 456/656 Fall 1998 Final Exam 6:00 PM, Tuesday, December 15, 1998, TBE B172

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.

Warning. There may be trick questions. Read each question very carefully! If a question calls for a proof of something that is false, the way to get partial credit is to state that it is false. The way to get full credit is to prove that it is false. The entire test is 200 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 recursive language is recursive.

(d) Every enumerable language is generated by some phase structure grammar.

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

(b) The universal language.

(c) Lsat, the set of satisfiable boolean expressions.

3. [10 points] Write a regular expression for the language L over the binary alphabet Σ = {0, 1} consisting of all binary numerals for positive integers that are equivalent to 1 modulo 3 (that is, numbers n for which n mod 3 = 1). Assume that no numeral has unnecessary leading zeros. For example, 1, 100, 111, 1010, 1101 are in L, but not 01.

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

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

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

(c) Anita has developed a new programming language with lots of useful features. But her professor asks her to write a program (in this new language) that emulates a universal Turing machine. Why is that important?

6. (a) [15 points] Define the term non-deterministic finite automaton.

(b) [15 points] Referring the definition you just wrote in (6a) define the language accepted by a nondeterministic finite automaton.

(c) [15 points] Define the term recursive partial function.

7. (a) [15 points] Define the term Polynomial time function. (b) [20 points] Define the term N P-complete.

8. [30 points] Let Σ = {0, 1}, the binary alphabet. Let L be the set of all strings w over Σ where the length of w is the square of an integer. Use the pumping lemma to prove that L is not a context-free language.