Theory of Computing Assignment 2
This assignment requires you to demonstrate your knowledge of the key concepts of
Turing machines, universality, computability and the Chomsky Hierarchy
COT-5310 Theory of Computation I Assignment 2 Florida International University Knight Foundation School of Computing and Information Sciences 1. (10 points) Find an equivalent NFA for the following regular expression in the alphabet Σ = {0, 1}: ( 0Σ+1(0 ∪ 10) ∪ 0(1 ∪ ε)Σ∗0 )∗ 2. (10 points) Convert the DFA below into a regular expression that describes exactly the same language. Eliminate states in the following order: q3, q1, q2. Show your work. q0start q1 q2 q3 0 1 1 0,1 0 1 3. (35 points) Find a regular expression which recognizes each of the following languages (in parts (b) and (c), assume that Σ is an arbitrary non-empty finite set of symbols and n is an arbitrary positive integer): (a) { w ∈ {a, b, c}∗|w contains at most two a’s and at most two b’s } (b) { w ∈ Σ∗| the length of w is at most n } (c) { w ∈ Σ∗| the length of w is not equal to n } (d) {w ∈ {a, b, c}∗| (every odd position of w is b or c) ∨ (every even position of w is a)} (e) {w ∈ {0, 1}∗|w 6= 0100 ∧ w 6= 101} 4. (10 points) Use pumping lemma to show that {0n1m|0 ≤ n ≤ m} is not a regular language. 5. (25 points) Are the following languages regular? (Prove your answers) (a) { a( n 2) ∈ {a}∗ ∣∣∣ n ∈ Z≥2} (b) { apbqab √ pqc ∈ {a, b}∗ ∣∣∣ p, q ∈ Z+} 1 (c) { apb2+qa2 ∈ {a, b}∗ ∣∣∣ p, q ∈ Z+} 6. (10 points) Let f : R+ 7→ R+ be a differentiable function and ∀x ∈ R+, f ′(x) ≥ dxe. Prove that {1df(n)e|n ∈ Z+} is not regular (Hint: use pumping lemma). 2 Computing Theory COSC 1107/1105 Assignment 2: Computability Assessment Type Individual assignment. Submit online via Canvas → As- signments → Assignment 1. Marks awarded for meeting re- quirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums. Due Date Week 12, Sunday 16th October 2022, 11:59pm Marks 110 worth 25% of your final assessment 1 Overview This assignment requires you to demonstrate your knowledge of the key concepts of Turing machines, universality, computability and the Chomsky Hierarchy. You are also required to report on some further experiments with the Platypus game. 2 Assessment details 1. Computability (15 marks) The generalised Platypus green game (GPGG) is defined as follows. Let M1 and M2 be Turing machines, which share the same tape. The tape is initially all green. The initial configuration of the two machines is as shown below. As in the Platypus game, each machine takes turns to move (but there is no scoring involved). (a) Show that the halting problem for GPGG is undecidable. You may use any reduction that you like. (6 marks) (b) Suppose the GPGG is played on a Turing machine with a finite tape (making the halting problem decidable), and that this problem has been shown to be NP-complete. Given your above reduction from some problem A to the GPGG, can this reduction be used to conclude that A is NP-complete? Why or why not? Explain your answer. (2 marks) (c) Seedout, a rather adventurous and reckless hobbit, has proposed the reduction below as a way of showing the Empty Language problem is undecidable by reducing the Halting Problem to it. Unfortunately there are two errors in this reduction. Identify these errors, explain why these are incorrect and how they may be corrected. (4 marks) Seedout’s explanation is: ”Assuming the Empty Language problem is decid- able (and hence the existence of a Turing machine Empty which decides the problem), we can construct a solution to the Halting Problem as follows. First, given the Turing machine M and input w, we use these to construct another Turning machine M ′′ which deletes any input on the tape, writes w on the tape and then acts as M would. So the language accepted by M ′′ is empty iff M halts on w. See the diagram below for more details.” (d) Undecidability results are often given in terms of Turing machines. Explain how these results are relevant to modern programming languages, using three examples of undecidable problems that occur in such languages. (3 marks) 2. Nondeterminism (8 marks) Consider the incomplete NFA M0 below, whose alphabet is {0, 1}. 2 Use M0 to create three more NFAs M1, M2 and M3 according to the constraints below. Explain in one or two English sentences how you constructed each NFA. Each of M1, M2 and M3 must contain at least 10 transitions (potentially but not necessarily including λ-transitions) and must be an NFA but not a DFA. Specifically there must be at least one combination of state and input (either 0 or 1) for which there are at least two possible states. Put another way, removing all λ-transitions must not result in a DFA. Use JFLAP to transform M1, M2 and M3 into equivalent DFAs. The sizes of the DFA resulting from the determinising algorithm must be as below. Note that the JFLAP implementation of this often omits an “error” state, i.e. it may be necessary to add an extra state to the result from JFLAP in order to account for this. The size constraints below assume a fully deter- ministic DFA; one way to check for this is that if the DFA has k states, there must be exactly 2k transitions (one for each of 0 and 1 in each state). (a) The size of the DFA corresponding to M1 is 2 or 3. (3 marks) (b) The size of the DFA corresponding to M2 is 5. (2 marks) (c) The size of the DFA corresponding to M3 is at least 9 (this may be harder than you think!) (3 marks) 3. Pumping Lemma (20 marks) (a) There are three errors in the statement of the Pumping Lemma for regular languages below. Find all three, state how to correct them, and explain your answers. (4 marks) Let L be a regular language. Then ∃n ≥ 1 such that for any w ∈ L such that |w| > n, ∃x, y, z such that w = xyz where 3 i. |xy| ≤ n ii. x ̸= λ iii. xyiz ∈ L for all i ≥ 1 (b) Galadriel, on her Elftiki tour of Middle-Earth in the Second Age, comes across some scraps of parchment in the Hall of Records of Numenor. These scraps, numbering 10 in all, are partly burned and not always legible, but contain some ancient runes that not even Galadriel can decipher. But she can make some educated guesses, and first must decide on the relevant order of the fragments, before choosing from potential translations for each of them, so that the overall message makes sense. The fragments are below, with the parts where there are alternative transla- tions labelled with capital letters, like this: (Translated text) A (Translated text) A1: Alternative 1 A2: Alternative 2 A3: Alternative 3 1: As the Pumping Lemma requires xyiz ∈ L, this is a A A1: paradox A2: problem A3: tautology A4: contradiction 2: so we have w ∈ L, |w| ≥ n and B, and so we have C for some 1 ≤ j ≤ n. B1: |xy| < n="" b2:="" |xy|="" ≤="" n="" b3:="" |xy|=""> n B4: |xy| ≥ n C1: y = 0j C2: y = 1j C3: y = 0j1j C4: y = (012)j 3: D and xyiz ∈ L for all i ≥ 0 D1: |y| = 0 D2: |y| ≠ 0 D3: |y| > 1 D4: |y| = 1 4: Then ∃n ≥ 1 such that E and F, E1: for all w ∈ L and |w| ≥ n E2: for all w ∈ L and |w| ≤ n E3: for some w ∈ L and |w| ≥ n E4: for some w ∈ L and |w| ≤ n F1: ∃x, y, z such that w = xyz, |xy| ≤ n F2: ∃x, y, z such that w = xyz, |xy| ≥ n F3: ∀x, y, z such that w = xyz, |xy| ≤ n F4: ∀x, y, z such that w = xyz, |xy| ≥ n 5: and so we have shown that our assumption is false, i.e. that G. G1: context-free G2: not regular G3: empty G4: regular 6: Beren’s tale: A proof that the language L = H is not I . H1: {ww|w ∈ {0, 1, 2}∗} H2: {w2w|w ∈ {0, 1, 2}∗} H3: {w1w|w ∈ {0, 1, 2}∗} H4: {w1w2w|w ∈ {0, 1, 2}∗} I1: context-free I2: regular I3: empty I4: recursively enumerable 7: and so xyiz is J J1: 1n+j21n J2: 0n+j0n J3: 0n−j10n20n J4: 1n+j11n20n 8: Let w be K. K1: 0n10n20n. K2: 1n21n. K3: 1n11n20n. K4: 0n10n. 9: Assume L is L. L1: not regular L2: regular L3: not context-free L4: context-free 4 10: Now consider M M1: i = 0 M2: i = 1 M3: i = 2 M4: i = 3 Re-assemble the proof for Galadriel. (6 marks) You do not need to write the proof out in full. You can submit your final version on Canvas. (c) The Pumping Lemma for regular languages states a necessary property for such languages. Is it possible that the same property is true for context-free and context-sensitive languages? Explain your answer. (3 marks) (d) Let L the language of a DFA with n states. Explain why either L = ∅ or there is a string w ∈ L such that |w| < n.="" (3="" marks).="" (e)="" the="" pumping="" lemma="" for="" context-free="" languages="" is="" below.="" let="" l="" be="" a="" context-free="" language.="" then="" there="" is="" an="" n="" ≥="" 1="" such="" that="" for="" any="" string="" w="" ∈="" l="" with="" |w|="" ≥="" n="" there="" exists="" strings="" x,="" y,="" z,="" u,="" v="" such="" that="" w="xyzuv" and="" i.="" |yzu|="" ≤="" n="" ii.="" |y|+="" |u|=""> 0 iii. xyizuiv ∈ L for all i ≥ 0 Use this to show that the language L = {ai3 | i ≥ 2} is not context-free by filling in the gaps below. (4 marks) Proof: Assume . So the Pumping Lemma applies, and so for any string w ∈ L with |w| ≥ n there exist strings x, y, z, u, v such that w = xyzuv and i. |yzu| ≤ n ii. |y|+ |u| > 0 iii. xyizuiv ∈ L for all i ≥ 0 Let . So w ∈ L and , and w = xyzuv, |yzu| ≤ n, |y| + |u| > 0 and xyizuiv ∈ L for all i ≥ 0. Now as , this means |yzu| = |y|+ |z|+ |u| ≤ n and so |y|+ |u| ≤ n. Let i = 0 and consider |xy0zu0v| = |xzv| = −|y|−|u| = n3−(|y|+ |u|) ≥