计算机理论代写 COSC1107/1105 Computing Theory Assignment 2

计算理论 Theory of Computation

COSC1107/1105 – Computing Theory Assignment 2 (15%)
Total marks: 100
Deadline: Sunday, the 14th of October, 2018 23:59

Please read all the following information before attempting your assignment. This is an individual assignment. You may not collude with any other individual, or plagiarise their work. Students are expected to present the results of their own thinking and writing. Never copy another student’s work (even if they “explain it to you first”) and never give your written work to others. Keep any conversation high-level and never show your solution to others. Never copy from the web or any other resource. Remember you are meant to generate the solution to the questions by yourself. Suspected collusion or plagiarism will be dealt with according to RMIT policy.

Submission Instructions: You will need to submit one PDF file via the following Google Submission Form:. https://tinyurl.com/rmitct18-ass2-sub

The PDF file can have any name as long its extension is .pdf. The file must be typeset in a word processor (scanned files will not be marked). When submitting your file using the form above, you must use your RMIT Student Email account. Refer to this FAQ.

Submissions not compatible with the instructions above will attract zero marks and do not warrant a re-submission.

In the submission form you will be required to certify that the submitted solution represents your own work only by agreeing to the following statement:

If you are not able to certify this, it is best not to submit anything.

Assignment Overview: This assignment has just three exercise around three topics: undecidability, complexity, and Pumping Lemma. The exercise are either conceptual questions or formal proofs. Topic for Exercise 3 has yet not been covered and will be discussed in Week 9. However, you should be able to work on Exercises 1 and 2 already and it is highly recommended you do that, so you can work on Exercise 3 alone later.

Corrections: From time to time, students or staff find errors (e.g., typos or wrong symbols) in the assignment specification. In that case, a corrected version will be uploaded to the course web page as quickly as possible, an announcement will be made on the course web page as well as in the forum. Check the version on the bottom left.

Forum postings on assignment: Never post any information on the forum that may disclose how to solve a question or what the solution may be. You may only post assignment related questions for clarification, for example, to clarify certain notation. Any post discussing possible solutions or strategies may directly be considered plagiarism, see above. If in doubt, do not post and ask your tutor the question instead. Remember that I do not wish to put the forum in a moderated mode, however, a breach of this policy will force me to do so. This would also mean that sometimes your questions may not get answered timely.

Silence Policy: A silence policy will take effect 48hrs before this assignment is due. This means no questions about this assignment will be answered, whether they are asked on the discussion board, by email, or in person. You must ensure that all your queries are resolved prior to those 48 hours, including questions about submission using Google form. You are reminded that leaving things until the last minute and any problem that ensues, are no grounds for extensions, re-submission or re-marking.

I certify that this is all my own original work. If I took any parts from elsewhere, then they were non-essential parts of the assignment, and they are clearly attributed in my submission. I will show I agree to this honour code by typing “Yes”:

1

COSC1107/1105 – Computing Theory Assignment 2 Page 2 of 4

Exercise1: Undecidability…………………………………………………………………….35marks

  1. (a)  (5 marks) One technique to show that a decision problem is undecidable is to reduce a known undecidable problem, like the Halting Problem, to the problem of concern. Explain what requirement on that reduction (besides being a reduction, of course) is fundamental for this approach to work. Also, state which Theorem in Sudkamp’s book makes use of this requirement.
  2. (b)  (15 marks) Prove that the problem of deciding whether a Turing Machine M halts on input w is undecidable. Use the fact that deciding whether a Turing Machine M accepts no input whatsoever, i.e., L(M ) = ∅, is undecidable.
  3. (c)  (15 marks) Consider the following two decision problems:
    P1: Given a Turing machine T and a string w, is there exactly one way that machine T can accept w?
    P2: Given a Turing machine T and a string w, does T accept w?
    Use the fact that problem P2 has already been shown undecidable (in the tutorial!), to prove that problem P1 is also undecidable.

Exercise2: Complexity……………………………………………………………………….25marks

  1. (a)  (8 marks) If f, g and h are non-decreasing complexity functions. Prove mathematically that if f(n) ∈ O(h(n)),

    then f(n) ∈ O(g ◦ h(n) + c), for any constant c ≥ 0, where a ◦ b is the composite function of a and b.

  2. (b)  (5 marks) One technique to show that a decision problem is NP-hard, is to reduce a known NP-hard problem, such as 3SAT, to the problem of concern. Explain what requirements, and why, on such reduction are fundamental for the approach to work. Also, state which Theorem in Sudkamp’s book makes use of this requirement.
  3. (c)  (5 marks) Suppose you are studying the computational complexity of a given problem X. It is known that the boolean satisfiability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class PSPACE, as somebody have already developed an algorithm for X that is guaranteed to provide a solution using a polynomial amount of space with the size of the input. Can it be the case that X is an NP-COMPLETE problem? Justify your answer and, if your answer is “yes,” state what would you need to do to show that X is NP-COMPLETE.
  4. (d)  (7 marks) Prove formally, via a suitable problem reduction, that the Exact 4SAT problem (i.e., determine the satisfi- ability of a formula in conjunctive normal form where each clause has exactly four literals) is NP-complete. Use the knowledge that the Exact 6SAT problem (i.e., determine the satisfiability of a formula in conjunctive normal form where each clause has exactly six literals) is NP-complete. An informal or incomplete argument will not constitute a proof.

Exercise 3: Pumping Lemma & Regularity………………………………………………………40 marks

  1. (a)  Complete the four missing requirements (i)-(iv) in the following statement:

    Pumping Lemma: Let L be a regular language. Then, there exists an integer n ≥ 1 such that for every w ∈ L with |w| ≥ n, there exist strings x, y, z ∈ Σ∗, such that:

    i. (1 mark) ii. (1 mark) iii. (1 mark) iv. (1 mark)

  2. (b)  (2 marks) Briefly explain in one or two sentences why the Pumping Lemma is useful and important.
  3. (c)  (10 marks) 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 = {wawR | w is any string over {a, b}}, over alphabet Σ = {a, b}, 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:

Version: September 16, 2018 Exercise 3 continues on the next page. . .

COSC1107/1105 – Computing Theory

Assignment 2

Page 3 of 4

Here is my proof for your request during your interview. To prove that L = {wawR | w is any string over {a, b}}, over alphabet Σ = {a, b}, is not regular, I will appeal to the well-known Pumping Lemma, that I studied during my Computing Theory course in 2018. If you are not familiar with it, you can check my lecturer Abhijeet Anand’s slides here. (These slides will be available after Week 9 lecture.)

Here are the other pieces they’ve transcribed: (a)

(b)

(c)

(d) (e) (f) (g)

(h) (i) (j)

(k)

(l)

(m) (n)

(o)

(p)

(q)

You need not write out the entire proof, just provide the corresponding letters in the correct order as a word in the submission form. 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. Your answer should be entered in the assignment submission form.

(d) (10 marks) Let L2 = {bkac2k | k ≥ 0}. Prove that there is no DFA for L2 by completing the following proof. Concretely, you need to fill each of the seven missing parts.

  1. Assume that there is a DFA M2 which accepts L2 and hence that .
  2. Then, by the Pumping Lemma from Exercise 3.(a) above applies for some n ≥ 1.

Thus, w = xyz such that |xy| ≤ k and |y| ≥ 1.

Consider now i = 0. Then, xyiz = xy0z = xz = abk−jabka, or xz = bk−j+1abka.

Then, it follows that w ∈ L and |w| ≥ k.

Consider now i = 2. Then, xyiz = xyyz = abkabjabka, or xyyz = abkbjabka.

Now consider w = abbbabbba.

Assume that L is regular. Then, there exists a k ∈ N as per the Pumping Lemma.

Thus we have a contradiction: our assumption (that L is regular) must be true and L is true.

Consider now i = 2. Then, xyiz = xyyz = abbbbbbabbba. It is then clear that xyiz ̸∈ L.

So, it follows that x = a, y = bbb, and z = abbba. Clearly w = abbbabbba = xyz.

Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular.

Then, it follows that w ∈ L and |w| = 9.

So,itfollowsthatyisoftheformabj forsome1≤j≤k−1,orisoftheformbj forsome1≤j≤k−1.

Now consider w = abkabka.

Clearly, either case implies, xyiz ̸∈ L because the symmetry is lost.

Now, because j < 0, this means that xyiz ∈ L.

So, there exist substrings x, y, z ∈ Σ∗ satisfying the four Pumping Lemma conditions.

So,itfollowsthatyisoftheformabj forsome1≤j≤k,orisoftheformbj forsome1≤j≤k.

  1. Then, consider string w =
  2. Clearly,w∈L2 and|w|>n.
  3. So, by the Pumping Lemma,
  4. Because |xy| ≤ n, it must be the case that
  5. Now consider the word w′ =
  6. By the Pumping Lemma, it follows that w′ ∈ L2.
  7. However,
  8. So we reach a contradiction, and L2 cannot be regular.
  9. Finally, due to

.

.

.
we know that a language is regular if and only if it

.
.

can be recognised by a DFA. Therefore, since L2 is not regular, there is no DFA that recgonises language L2.

  1. (e)  (10 marks) Let L3 = {1n0k14n | n ≥ 0,k > 0}. Prove that there is no DFA M3 for L3 such that L(M3) = L3.
  2. (f)  (4 marks) Let L4 = {a, b}∗ \ {wawR | w is any string over {a, b}} be a language over Σ = {a, b}. Prove that there is no DFA M4 such that L(M4) = L4. Your proof should be short and not use the Pumping Lemma.

Version: September 16, 2018

Exercise 3 continues on the next page. . .

End of Assignment 2

COSC1107/1105 – Computing Theory Assignment 2 Page 4 of 4

Question

Points

Undecidability

35

Complexity

25

Pumping Lemma & Regularity

40

Total:

100

Version: September 16, 2018

Related Posts