## Decidability-and-Undecidability

 Question 1

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G1 and G2, whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language

Which one of the following statement is correct?

 A Only I and II are undecidable B Only III is undecidable C Only II and IV are undecidable D Only I, II and III are undecidable
Theory-of-Computation       Decidability-and-Undecidability       Gate 2018
Question 1 Explanation:
IV is trivial property, as every regular language is CFL also, so a language which has NFA must be regular and for every regular language we can have a deterministic PDA (as every regular language is DCFL).
I, II and III is undecidable.
 Question 2

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.

Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
 A I and IV only B II and III only C II, III and IV only D III and IV only
Theory-of-Computation       Decidability-and-Undecidability       GATE 2017(set-02)
Question 2 Explanation:
Since membership problem for regular language is decidable, so I is decidable.
Emptiness problem for Context free language is decidable, so II is decidable.
Completeness problem (i.e. L(G) = Σ* for a CFG G) is undecidable.
Membership problem for recursive enumerable language (as language of Turing Machine is recursive enumerable) is undecidable.
So IV is undecidable.
 Question 3

Which of the following decision problems are undecidable?

I. Given NFAs N1 and N2, is L(N1)∩L(N2) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?

 A I and IV only B II and III only C III and IV only D II and IV only
Theory-of-Computation       Decidability-and-Undecidability       2016 set-01
Question 3 Explanation:
Statement I is decidable, as we can make product automata by using N1 and N2 and can decide whether the resulting Product automata’s language is phi or not.
Statement II is decidable, as for CFG we have membership algorithm, hence it is decidable.
But for problems in statement III and IV, there doesn’t exist any algorithm which can decide it.
 Question 4
 A Only II B Only III C Only I and II D Only I and III
Theory-of-Computation       Decidability-and-Undecidability       GATE 2015 -(Set-2)
Question 4 Explanation:
I. True.
Turing decidable language are recursive language which is closed under complementation.
II. False.
All language which is in NP are turing decidable.
III. True.
 Question 5
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*.  Which one of the following is TRUE?
 A Both 2Σ* and Σ* are countable B 2Σ* is countable and Σ* is uncountable C 2Σ* is uncountable and Σ* is countable D Both 2Σ* and Σ* are uncountable
Theory-of-Computation       Decidability-and-Undecidability       Gate 2014 Set -03
Question 5 Explanation:
If = {0,1} then Σ* ={ϵ, 0, 1, 00, 01, 10, 11, 000,...............}
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2Σ* is uncountable, it has been already proved by using Diagonalization method.
 Question 6
 A 1, 2, 3, 4 B 1, 2 C 2, 3, 4 D 3, 4
Theory-of-Computation       Decidability-and-Undecidability       Gate 2012
Question 6 Explanation:
The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.
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 7
 A I and II B I and IV C II and III D II and IV
Theory-of-Computation       Decidability-and-Undecidability       Gate-2008
Question 7 Explanation:
The intersection of two regular languages is always a regular language (by closure property of regular language) and testing infiniteness of regular language is decidable. Hence statement I is decidable.
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given context-free language is regular and whether two push-down automata accept the same language.
 Question 8
Which of the following problems is undecidable?
 A Membership problem for CFGs. B Ambiguity problem for CFGs. C Finiteness problem for FSAs. D Equivalence problem for FSAs.
Theory-of-Computation       Decidability-and-Undecidability       Gate-2007
Question 8 Explanation:
Whether a given CFG is ambiguous, this problem is undecidable. The reason is there is no algorithm exist for this. Remaining all are decidable.
 Question 9
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
 A P3 is decidable if P1 is reducible to P3 B P3 is undecidable if P3 is reducible to P2 C P3 is undecidable if P2 is reducible to P3 D P3 is decidable if P3 is reducible to P2's complement
Theory-of-Computation       Decidability-and-Undecidability       Gate-2005
Question 9 Explanation:
Option A: If P1 is reducible tido P3 then P3 is atleast as hard as P1. So there is no guarantee if P3 is decidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can't say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
 Question 10
 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
Theory-of-Computation       Decidability-and-Undecidability       Gate-2003
Question 10 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 11
 A Both (P1) and (P2) are decidable B Neither (P1) nor (P2) are decidable C Only (P1) is decidable D Only (P2) is decidable
Theory-of-Computation       Decidability-and-Undecidability       Gate-2000
Question 11 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 12
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
Theory-of-Computation       Decidability-and-Undecidability       Gate-1997
Question 12 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 13
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).
Theory-of-Computation       Decidability-and-Undecidability       Gate-1996
Question 13 Explanation:
Equivalenceof 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 14
 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).
Theory-of-Computation       Decidability-and-Undecidability       Gate-1990
Question 14 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 behaviour of TM unknown hence, undecidable.
There are 14 questions to complete.