Reference no: EM132383172
COSC1107/1105 - Computing Theory
Assignment 2
Exercise 1: Turing Machine Design
In this exercise you will build a few Turing Machines in JFLAP. Your machines will be fully automarked, so you must follow the following conventions (please read them carefully and ask if in doubt1):
• Your Turing machine will always start with the head in the first symbol of the input on the tape. For example, if your initial state is q0 and the input string is abcd#cba, then the initial configuration would be q0, Babcd#cbaB, where B is the blank symbol (in red for better legibility), and the underlined symbol is where the head is reading. Note this is a different convention to that used in many machines done in tutorials where the head was assumed to begin reading the blank symbol on the left of the input, and so one must do a B/B,R initial transition.
• The acceptance condition to be used will be halting in a final state, as in the Sudkamp's book. - JFLAP has two acceptance conditions under Preferences, one can make JFLAP "Accept by final state" or "Accept by halting", or by either of them (if both selected). We recommend to work with only "Accept by final state" selected, but remember that by itself "Accept by Final State" does not require halting, so think how to build your machine to capture the halting in final state acceptance condition that shall be used.
• The output of a Turing machine (when it accepts) consists of the character directly under the tape head until the first blank to the right consists of the symbol underneath the tape head and all symbols to the right of the tape head until the blank is encountered. In the event that the tape head is on a blank, the output is the empty string. For example, if the Turing Machine accepts with the tape left as Baaaaabcd#cbaB, then the output of the Turing Machine is the string abcd#cba. When a Turing Machine rejects, what is left in the tape is irrelevant-there is no output.
• Your machines must be syntactically error-free, and load and terminate always within a reasonable amount of time using JFLAP version 7: at most 5 secs. per run. These two are minimal standards that must be met. Machines with syntactic errors or requiring more than 5 seconds on any input will be awarded zero marks.
• No manual changes or repairs will be done to any of the submitted files. It is your responsibility to test your files in JFLAP 7 before submitting (you have the tool!).
• Your TM has to be one-tape standard "Turing Machine" in JFLAP (no multi-tape machine or block machine); refer to post @151. You are free however to use any advanced features provided by JFLAP for standard Turing Machines, as long as the machine submitted solves the problem. Please refer to some information and tips on JFLAP at the end of the document.
• You can assume that any input given to your machine will have the correct shape, so you do not need to check for the input having a valid form. (a) (8 marks) [E1-Qa1.jff] Build a deterministic Turing machine that takes two words w1,w2 ∈ {a, b, c, d}∗, separated by a # symbol in the form Bw1#w2B and determines (by accepting/rejecting) whether string w2 is a substring of w1. (b) (8 marks) [E1-Qb1.jff] Build a deterministic Turing machine that takes an input string w ∈ {a, b, c, d}∗ and replaces it with wr, the reverse of w. After reversing the string, the machine must accept. For example:
• When run on input BabcdabcdB, it should leave BdcbadcbaB on the tape.
• When run on input BaaaaaaaaB, it should output BaaaaaaaaB.
• When run on input BabccdabcddacB, it should output BcaddcbadccbaB. Remember the output starts on the symbol the head is left until the first blank on the right. Also recall the machine must always accept (after producing the output, of course!). (c) (4 marks) [E1-Qc1.jff] Combine your machines to produce a single deterministic machine that takes an input of a substring the form of Bww1#w1), the 2B machine and if if rejects. w2 is a When substring rejecting, of w1, it it does replaces not matter w1 with what w1 rand is left accepts; on the otherwise tape (i.e., (if the wtape 2 is can not be left in any way). For example:
• When run on input B
{ abcdabcdabcd#
w}} 1 { { abcda w}} 2 { B it should accept and leave B
{ dcbadcbadcba#
w}} r1 { { abcda w}} 2 { B on the tape.
• When run on input B
{ bbbbaaaaa#
w}} 1 { { aaabaaa w}} 2 { B, it should just reject (what is left on the tape is irrelevant).
1If anything is unclear here, or if you are stuck, you can ask general questions about JFLAP or Turing machines on the discussion board, or otherwise come and see Sebastian or Angus at one of their consultation times.
Exercise 2: Undecidability
Let L1 = {M | M is a TM that halts on the empty tape leaving exactly two words on its tape in the form Bw1Bw2B}.
(a) You have seen the proof in tutorial 7 (PART 2) that ATM, the problem of deciding whether an arbitrary Turing machine will accept an arbitrary input, is undecidable. Use this result to prove, formally using problem reduction, that given an arbitrary Turing machine M, the problem of deciding if M ∈ L1 is undecidable.
(b) Is L1 recursive, recursively enumerable, non-recursively enumerable, uncomputable? Justify your answer.
Exercise 3: Complexity
(a) Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time O(h(g(n)) +c), for any constant c ≥ 0 and any functions g(n) and h(n) where h(n) ≥ n.
(b) A cutting-edge publisher based in Melbourne is publishing a book on complexity theory. They learnt that you are taking Computing Theory at RMIT, so they offered you a very well paid job! For the job, you are asked to write the part of the book that explains the following picture:
R
LOG Time
Your text will go to a proper book, so it has to be professional, well written, and clear. And of course, you are to explain the figure the best way possible! The publisher told you that you can use no more than one page.(c) U (1.e, S Consider ⊆ 2U) where the following U roblem SC: "given a set of elements U = {u1, u2, ..., un} and a set S of subsets
s∈S
ELEMENTARY . 2EXPTIME
EXPSPACE EXPTIME PSPACE
o-NPTIME
c
PTIME NPC LOG
N
PTIME
Space
s = U, find the smallest set C⊆S such that ? c∈C
c = U?"
The SC problem is a very famous one, and one much studied. Explain why stating that SC is the NP-complete complexity class (or SC is an NP-complete problem) would be technically incorrect to say. Note: A perfect answer can be stated in no more than 3 short sentences. (d) (5 points (bonus)) In no more than half a page, explain and discuss the the phase transition phenomenon in random Random 3-SAT. Note: This requires some research. Marks will depend on quality of presentation, and depth and breath of the explanation.
Exercise 4: Pumping Lemma & Regularity
(a) It is Novemeber 2021. Because you did so well in Computing Theory in 2019, the course instructor (a strange guy with a weird accent who walks a lot during lectures) asked you to tutor for it, which of course you accepted given how much you liked the course! The term is almost over, and it is exam marking time. In one of the questions, students were asked to state the Pumping Lemma for regular languages. The question is worth 10 marks. You take the next exam to mark and you read the following answer from the
student:
P °u‹m ¯p °i‹n`g L`e›m‹m`affl: L`e?t L b~ fle `affl °r`e ´g?u l~ ´a °rffl l~ ´a‹n`g?u`a`g ´e. T‚h`e›nffl, f~ ´o ?rffl `e›vfle?r‹y
°i‹n °t ´e ´g ´e?rffl n ≥ 1 `a‹n`dffl
`e›vfle?r‹y w ∈ L "w ?i °t‚hffl |w| ≥ n, °t‚h`e?r`e `e›x?i ¯sfi °t ¯sfi °t?r °i‹n`g ?s x,y,z ∈ Σ∗, ¯sfi °u`c‚hffl °t‚h`a °t °t‚h`e
~f ´o ?l ¨l ´o"w ?i‹n`g ?h`o ?l ´d ¯s:
1. w = xyz; 2. |xy| ≤ n; 3. y = ε; `a‹n`dffl 4. xyiz ∈ L, f~ ´o ?rffl `a l~ ¨l i ≥ 0.
You are amazed by the student's handwriting (it is just beautiful!). To mark it, you are asked to:
1. Specify how many marks you will award to the student's answer.
2. If you found the answer wrong, provide detailed feedback to the student in one paragraph. Just identifying the mistake(s) is not enough, you must explain to the student why the answer is wrong, how it would not work, etc. Be as clear, complete, and intuitive as possible to help the student to learn the Pumping Lemma!
(b) Emma's Pumping Lemma Dilemma: For her job interview in a highly-regarded software company, an ex-student of CT, Emma, has been asked to prove that L = {yyy | y ∈ {0,1}∗}, over alphabet Σ = {0,1}, is not a regular language. She was allowed to submit her proof the next day. That night, she finally finished the proof, wrote it all down neatly, and went to bed. During the night, burglars came into her house with their dog, and the dog chewed up her proof. In an attempt to cover their tracks, the burglars, who also happened to have taken CT years before, tried to recreate the proof. They gathered all the shreds they could find, but on some of them the ink had washed out from the dog's saliva, and so they couldn't read some parts of it. Can you help them put the proof back together? For each shred they found, they rewrote it on a piece of paper. If they couldn't rewrite it, they wrote different interpretations of what they thought it should say onto different pieces of paper. Now they have many pieces of paper, but they don't know which of them are correct and in which order they need to go. Help Emma's burglars! There is one big piece, that reads:
Here is my proof for your request during your interview. To prove that L = {yyy | y ∈ {0,1}∗}, over alphabet Σ = {0,1}, is not regular, I will appeal to the well-known Pumping Lemma, that I studied during my Computing Theory course in 2014. If you are not familiar with it, you can check my lecturer Sebastian Sardina's slides here.
Here are the other pieces they've transcribed:
(a) Now consider w = (0k10k10k1).
(b) Now consider w = (01)k(01)k(01)k.
(c) Then, it follows that w ∈ L and |w| = 3k + 3 ≥ k.
(d) Then, it follows that w ∈ L and |w| = 6k ≥ k.
(e) So, according to the Pumping lemma, there exist substrings x,y,z ∈ Σ∗ such that (1)-(4) hold.
(f) Thus w = 0k10k10k1 = xyz such that |xy| ≤ k and |y| ≥ 1.
(g) Thus w = (01)k(01)k(01)k = xyz such that |xy| ≤ k and |y| ≥ 1.
(h) So, it follows that x = 0q,y = 0r,z = 0s10k10k1, where q + r ≤ k, r ≥ 1, s ≥ 0, and q + r + s = k.
(i) So, it follows that x = uq,y = ur,z = usukuk, where u = 01,q + r ≤ k, r ≥ 1, s ≥ 0, and q + r + s = 2k.
(j) Consider now i = 0. Then, xyiz = xy0z = xz = 0q0s10k10k1=0q+s10k10k1.
(k) Consider now i = 0. Then, xyiz = xy0z = xz = (01)q(01)s(01)k(01)k = (01)q+s(01)k(01)k.
(l) Now, because q + r + s = k and r ≥ 1, we know that q + s = k, and therefore, xyiz ∈ L.
(m) Assume that L is regular. Then, there exists a k ∈ N as per the Pumping Lemma.
(n) Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular.
(o) Thus we have a contradiction: our assumption (that L is regular) must be true and L is true. You need not write out the entire proof, just provide the corresponding letters in the correct order as a word. For example, the word badf denotes the proof built from statements (b), (a), (d), and (f) in that exact order. And remember: the burglars wrote down multiple different interpretations of the same piece of the proof, so not all of these will be necessary or correct. However, all necessary pieces are listed above. (c) (9 marks) Let L = {a(n+3)(n-2)
| n ≥ 2}. Prove that there is no DFA for L by completing the following proof.
Concretely, you need to fill each of the six missing parts.
1. Assume that there is a DFA M which accepts L and hence that language L is regular. 2. Then, the Pumping Lemma applies for some n ≥ 1.
3. Then, consider string w = , where k>n. 4. Clearly, w ∈ L and |w| > n. 5. So, by the Pumping Lemma, there exist words x,y,z such that w = xyz with , y = ε, and
xyiz ∈ L for all i ≥ 0.
6. Because |xy| ≤ n<k, it must be the case that . 7. Now consider the word w = . 8. By the Pumping Lemma, it follows that w ∈ L. 9. However, . 10. So we reach a contradiction, and L cannot be regular.
11. Finally, due to the we know that a language is regular if and only if it can be recognised by a DFA. Therefore, since L is not regular, there is no DFA that recgonises language L. (d) (4 marks) Let L2 = {0,1}∗ \ {yyy | y ∈ {0,1}∗} be a language over Σ = {0,1}. Prove that there is no DFA M such that L(M) = L2. Your proof should be short and not use the Pumping Lemma.
Attachment:- Computing.rar