## Decidability-and-Undecidability

Question 1 |

L

_{1}=〈M〉|M takes more than 2021 steps on all inputs

L

_{2}=〈M〉|M takes more than 2021 steps on some input

Which one of the following options is correct?

Both L _{1}and L_{2} are undecidable. | |

L _{1}is undecidable and L_{2}is decidable. | |

L _{1}is decidable and L_{2}is undecidable. | |

Both L _{1}and L_{2} are decidable. |

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 2 |

Which of the following languages are undecidable? Note that

- L

_{1}=

L

_{2}= {

L

_{3}= {

L

_{4}= {

L _{2} and L_{3} only
| |

L _{1} and L_{3} only
| |

L _{2}, L_{3} and L_{4} only | |

L _{1}, L_{3} and L_{4} only |

_{1}is undecidable as emptiness problem of Turing machine is undecidable. L

_{3}is undecidable since there is no algorithm to check whether a given TM accept recursive language. L

_{4}is undecidable as it is similar to membership problem.

Only L

_{3}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 3 |

Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is a context-free language, then, is also context-free?

3) If L is a regular language, then, is also regular?

4) If L is a recursive language, then, is also recursive?

1, 2, 3, 4 | |

1, 2 | |

2, 3, 4 | |

3, 4 |

Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.

Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.

Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.

Question 4 |

Which of the following statements is false?

The Halting problem of Turing machines is undecidable. | |

Determining whether a context-free grammar is ambiguous is undecidbale. | |

Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2). | |

Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2). |

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 1

^{st}for CSL and REC.

→ None for RE.

Question 5 |

Which one of the following is not decidable?

Given a Turing machine M, a stings s and an integer k, M accepts s within k steps | |

Equivalence of two given Turing machines | |

Language accepted by a given finite state machine is not empty | |

Language generated by a context free grammar is non empty |

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 6 |

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?

Both (P1) and (P2) are decidable | |

Neither (P1) nor (P2) are decidable | |

Only (P1) is decidable | |

Only (P2) is decidable |

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 7 |

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

Which of the following CANNOT be true?

L _{1} ∈ P and L_{2} is finite | |

L _{1} ∈ NP and L_{2} ∈ P
| |

L _{1} is undecidable and L_{2} is decidable | |

L _{1} is recursively enumerable and L_{2} is recursive |

_{1}is polynomial time reducible to L

_{2}.

Now if L

_{2}is decidable then L

_{1}should also be decidable. Hence, option (c) is wrong.