Spring 2008 - 91.502 - Theoretical FoundationsComputer Science DepartmentUniversity of Massachusetts LowellLowell, MA 01854April 14, 2008.Name:1. 2. 3. 4. 5. 6. 7.Total: /50Exam Time: 1h & 15m. Each problem is worth 10 points. 50 pts total. Choose any 5 problems.Let me know which 5 should be graded.1. Context-Free Languages. Is the language{aibjck| i + j 6= k + 1, i ≥ 0, j ≥ 0, k ≥ 0}context-free? Either construct a grammar for it or prove that it is not.Note: This is a simplified version of homework 3.2.2e.Solution. The language is Context-Free. Probably the easiest way to go is to construct twogrammars, one forL1= {aibjck| i + j ≤ k, i ≥ 0, j ≥ 0, k ≥ 0}and the other forL2= {aibjck| i + j ≥ k + 2, i ≥ 0, j ≥ 0, k ≥ 0}and then to use the grammar construction for unions of Context-Free languages.L1:S1→  | S1c | A | B.A →  | aAc | B.B →  | bBc.1L2:S2→ a2D | abE | bbE.D →  | aD | aDc |E.E →  | bE | bEc.L: S → S1| S2.2. Context-Free Languages.(4 pts) Define strong LL(k) grammar.(6 pts) Is the grammarS → S1$, S1→ aaS1b | bb | aba strong LL(k) grammar for some k > 0? Prove your claim.Solution. For the definition of a strong LL(k) grammar, see p. 120 of the textbook.To find if a k > 0 exists, we first observe that there is only one rule of the form S → S1$,and so the partitioning of LAk(S) for any k > 0 is immediate (= one partition). To find ifthere is a k > 0 that will partition LAk(S1) we start by computing LA1(S1→ aaS1b) = {a},LA1(S1→ bb) = {b}, LA1(S1→ ab) = {a}. Thus LA1(S1) is not partitioned into disjointsubsets, and the grammar cannot be strong LL(1). We up the value of k to 2: LA2(S1→aaS1b) = {aa}, LA2(S1→ bb) = {bb}, LA2(S1→ ab) = {ab}. The three sets are disjoint andthus the grammar is strong LL(2).3. Context-Free Languages. Construct a pushdown automaton that accepts the language{0n1m| m 6= n, m 6= 2n}.Note: this is a simplified version of homework problem 3.5.3a.Solution. Although it may be possible to solve this problem directly, the easiest (i.e., leastclever) way is to construct three small grammars, for L1= {0n1m| m < n}, L2= {0n1m| n <m < 2n}, L3= {0n1m| m > 2n}, follwed by the NPDA construction from a Context-FreeGrammar that is the union of the three grammars.S → S1| S2| S3,S1→ 0 | 0S1| 0S11S2→ 00111 | 0S21 | 0S211S3→ 1 | S31 | 0S311.The NPDA constructed for L1is given below; the complete automaton requires filling in therest of the details for the other two grammar fragments (which would have been obvious -and unnecessary - at that point).2Note that I use & in place of , since I haven’t figured out how to use symbols (i.e., Greekletters) in GraphViz4. Turing Machines.(4 pts) Define Deterministic Turing Machine. Follow the definition in the textbook.(6 pts) Construct a DTM to compute the function f(m, n) = max(m, n) over naturalnumbers m, n. You may use a graph, a table detailing the transition function or a carefulverbal description that can be easily and unequivocally translated into one of the other twoformalisms.Solution. For the first part, see p. 160, in particular the description of the quintuple andthe transition function. Waving hands over pictures is fine, but you must describe the variousparts and the transition function in a way that is unequivocal, and leaving as little as possibleto intuition.The DTM. This should have been a 1-tape DTM, since that is what you defined - if youwanted to use another definition of DTM, more convenient for the computation, you shouldhave proven the equivalence. We start with the configuration:B 1 1 ... 1 1 B 1 1 ... 1 Bwhere m is the number of 1s in the first block and n is the number of 1s in the second block.A way to solve the problem could be:1) as you move left from the rightmost (third) B you find a 1 or a B.2) If you find a B (you have eliminated all the 1s of n (m ≥ n) or there were none(n = 0)), move to the left changing 1’s to 1s until you find a 1 or the leftmost B, move rightto the other B and halt;3) if you find a 1 change it to a B, move to the left until you find a B, then move to theleft until you find a 1 or a B;4) if you find a B, n > m and all you need to do is move left, changing 1’ to 1, the secondB to a 1, and keep going until you find a B; halt;35) if you find a 1, change it to a 1’ and keep moving right until you find the second B;goto 1).5. Primitive Recursion. Given the function definitionf(n) =(1 if n is the sum of two primes0 otherwise,prove that f (n) is primitive recursive. You must at least identify what primitive recursivefunctions and predicates you need in order to prove your claim, and provide the correctcomposition.Solution. A solution would be given byf(n) = (∃i≤ni)(and(prime(i), prime(minus(n, i))))minus (Ex. 4.24) is known to be primitive recursive, bounded existential quantification isprimitive recursive (Thm. 4.29b), and (Ex. 4.26b) is primitive recursive, and prime (Ex.4.30c) is also primitive recursive. Since f (n) is a bounded existential quantification of com-positions of primitive recursive functions, we are done. There are several other, slightly morecomplex ways of computing the same function. The main point was to use functions thatwere known from the course to be primitive recursive.6. Recursive and r.e. Sets.(5 pts) State the Projection Theorem.(5 pts) Prove that the range of a partial recursive function f : {0, 1}∗→ {0, 1}∗is arecursively enumerable set.Hint: every element of the range must be printable after a finite amount of moves by theappropriate Turing machine.Solution. For the first part, Thm 5.8 (p. 233); for the se cond part, Ex. 5.12, p. 236.7. Reducibility and Decidability.(2 pts) Define many-to-one reducible.(2 pts) Define complete with respect to many-to-one reducibility.(6 pts) By explicitly constructing a reduction from any r.e. set B to the set K = {n | n ∈Wn} = {n | (∃t)halt(n, n, t)}, show that K is complete w.r.t. many-to-one reducibility.Hint: this requires applying the Enumeration Theorem and the s-n-m Theorem to constructan appropriate (i.e., recursive) reduction function.Solution. For the first part, p. 236, near bottom; for the second and third parts, p. 251,Ex. 5.29 and the paragraph immediately preceding