Decidability-and-Undecidability

Question 1

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

    L1 = | L(M) = Φ}
    L2 = {| M on input w reaches state q in exactly 100 steps}
    L3 = {| L(M) is not recursive}
    L4 = {| L(M) contains at least 21 members}
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
Question 1 Explanation: 
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 2

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
Question 2 Explanation: 
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Question 3

Which one of the following is not decidable?

A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
Question 3 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 4

Consider the following decision problems:

    (P1) Does a given finite state machine accept a given string
    (P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?

A
Both (P1) and (P2) are decidable
B
Neither (P1) nor (P2) are decidable
C
Only (P1) is decidable
D
Only (P2) is decidable
Question 4 Explanation: 
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.
Question 5

Consider two languages L1 and L2 each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L1 iff f(x) ∈ L2]. Further, let f-1 be also polynomial time computable.

Which of the following CANNOT be true?

A
L1 ∈ P and L2 is finite
B
L1 ∈ NP and L2 ∈ P
C
L1 is undecidable and L2 is decidable
D
L1 is recursively enumerable and L2 is recursive
Question 5 Explanation: 
L1 is polynomial time reducible to L2.
Now if L2 is decidable then L1 should also be decidable. Hence, option (c) is wrong.
Question 6
 For a Turing machine M, <M> denotes an encoding of M. Consider the following two languages.
        L1=〈M〉|M takes more than 2021 steps on all inputs
L2=〈M〉|M takes more than 2021 steps on some input
Which one of the following options is correct?
A
Both L1and L2 are undecidable.
B
L1is undecidable and L2is decidable.
C
L1is decidable and L2is undecidable.
D
Both L1and L2 are decidable.
Question 6 Explanation: 

L1 is decidable. 

We can take all strings of length zero to length 2021.

If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.

If TM takes less than 2021 steps:

In such a case suppose TM  takes less than 2021 steps (let's say  2020 steps ) for string length 2021, 2022, 2023, then definitely TM  will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.

 

Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.

Question 7

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:
A
An arbitrary Turing machine halts after 100 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the products of two numbers.
D
None of the above.
E
Both (B) and (C).
Question 7 Explanation: 
A) An arbitrary TM halts after 100 steps is decidable. We can run TM for 100 steps and conclude that.
B) A TM prints a specific letter is undecidable.
C) A TM computes the products of two numbers is undecidable. Eventhough we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, undecidable.
There are 7 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access