Problem 5 For each of the following languages over the alphabet ? 0,1 }, indicat

Question

Problem 5 For each of the following languages over the alphabet ? 0,1 }, indicate whether the language is decidable and prove your answer: (a) A = { 1 01 e L(M) where M is a TM } (b) B = { | M is a TM that accepts 01 in at most 20 steps } (c) C= { | M is a TM that accepts 01 in more than 20 steps } CISC 631 Winter 2018 Final Exanm Problem 6 Give a mapping reduction from ATM-KMw Mis a TM and M accepts w) to the language B = { I Q is a TM that recognizes an infinite language} Problem 7 Consider the problem Q-{

Explanation / Answer

Problem 5:-

a) The Language is decidable because the Turing Machine will accept the string 01 which belongs to the Language L(M) and it will halt after accepting the input string. So, from this, we can conclude that A is Decidable language

b) The Language is decidable because the Turing Machine will accept the string 01 is at most 20 steps of iteration (ie. Maximum it will take 20 steps to accept the string 01) and after those many steps it will halt. So, from this, we can conclude that B is Decidable language.

c) The Language is Not-Decidable because the Turing machine will although accept the string 01 but we dont know when the TM is going to halt after iterating 20 steps (i.e Whether it will halt after 30 steps, 40 steps or 100 steps,....), we cannot predict on the number of iterations as to when the TM will halt. Since the Halting decision of TM cannot be justified from this, hence C is Not-Decidable Language.

Problem 6 -

B = {<Q, w*> | Q is a TM that accepts set of all strings over w*}. As we all know L = {w* | w belongs to {0,1}} is a Infinite Language because it can accepts infinite number of strings. ie. L = {null, 0,1,00,11,010,110,0011,1100,.......}. Clearly this shows that L is an Infinite Language.

Problem 7 -

Let us take a scenario:-

C1 = {red, green}, C2 = {red}, C3 = {green}. Thus S = <C1, C2, C3>, such that S is a finite set as it has 3 elements in it and each of Ci contains unique colored elements. This problem is considered as NP-Complete since we can find out the the solution in Polynomial Time and the solution does exists, but we cannot determine the collection Ci the order in which we can choose them. We can choose C1, C2, C3 or C3, C2, C1 or C2, C3, C1. Thus the selection of Ci in the Set S is non deterministic but we can certainly solve this problem in a polynomial amount of time. Hence Q is NP-Complete.

Please let me know in case of any clarifications required. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.