DecidabilityandUndecidability
Question 1 
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.
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 
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.
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 
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 G_{1} and G_{2}, whether L(G_{1}) = L(G_{2})
(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?
Only I and II are undecidable
 
Only III is undecidable  
Only II and IV are undecidable  
Only I, II and III are undecidable

Question 2 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.
I, II and III is undecidable.
Question 3 
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 contextfree grammar G, is L(G) = ∅?
III. Given a contextfree grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
I and IV only  
II and III only  
II, III and IV only  
III and IV only 
Question 3 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.
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 4 
Which of the following decision problems are undecidable?

I. Given NFAs N_{1} and N_{2}, is L(N_{1})∩L(N_{2})
= Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G_{1} and G_{2}, is L(G_{1}) = L(G_{2})?
IV. Given a TM M, is L(M) = Φ?
I and IV only  
II and III only  
III and IV only  
II and IV only 
Question 4 Explanation:
Statement I is decidable, as we can make product automata by using N_{1} and N_{2} 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.
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 5 
Only II  
Only III  
Only I and II  
Only I and III 
Question 5 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.
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 6 
Let Σ be a finite nonempty alphabet and let 2^{Σ*} be the power set of Σ*. Which one of the following is TRUE?
Both 2^{Σ*} and Σ* are countable  
2^{Σ*} is countable and Σ* is uncountable  
2^{Σ*} is uncountable and Σ* is countable  
Both 2^{Σ*} and Σ* are uncountable 
Question 6 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.
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 7 
1, 2, 3, 4  
1, 2  
2, 3, 4  
3, 4 
Question 7 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 nonfinal states and viceversa. 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.
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 nonfinal states and viceversa. 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 8 
Which of the following are decidable?
I.Whether the intersection of two regular languages is infinite
II.Whether a given contextfree language is regular
III.Whether two pushdown automata accept the same language
IV.Whether a given grammar is contextfree
I and II  
I and IV  
II and III
 
II and IV

Question 8 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 contextfree language is regular and whether two pushdown automata accept the same language.
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 contextfree language is regular and whether two pushdown automata accept the same language.
Question 9 
Which of the following problems is undecidable?
Membership problem for CFGs.
 
Ambiguity problem for CFGs.
 
Finiteness problem for FSAs.  
Equivalence problem for FSAs.

Question 9 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 10 
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?
P_{3} is decidable if P_{1} is reducible to P_{3}
 
P_{3} is undecidable if P_{3} is reducible to P_{2}  
P_{3} is undecidable if P_{2} is reducible to P_{3}  
P_{3} is decidable if P_{3} is reducible to P_{2}'s complement

Question 10 Explanation:
Option A: If P_{1} is reducible tido P_{3} then P_{3} is atleast as hard as P_{1}. So there is no guarantee if P_{3} is decidable.
Option B: If P_{3} is reducible to P_{2}, then P_{3} cannot be harder than P_{2}. But P_{2} being undecidable, this can't say P_{3} is undecidable.
Option C: If P_{2} is reducible to P_{3}, then P_{3} is atleast as hard as P_{2}. Since, P_{2} is undecidable. This means P_{3} is also undecidable.
Option B: If P_{3} is reducible to P_{2}, then P_{3} cannot be harder than P_{2}. But P_{2} being undecidable, this can't say P_{3} is undecidable.
Option C: If P_{2} is reducible to P_{3}, then P_{3} is atleast as hard as P_{2}. Since, P_{2} is undecidable. This means P_{3} is also undecidable.
Question 11 
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?
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 
Question 11 Explanation:
L_{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.
Now if L_{2} is decidable then L_{1} should also be decidable. Hence, option (c) is wrong.
Question 12 
Both (P1) and (P2) are decidable  
Neither (P1) nor (P2) are decidable  
Only (P1) is decidable  
Only (P2) is decidable 
Question 12 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.
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 13 
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 
Question 13 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.
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 14 
Which of the following statements is false?
The Halting problem of Turing machines is undecidable.  
Determining whether a contextfree grammar is ambiguous is undecidbale.  
Given two arbitrary contextfree 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). 
Question 14 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 1^{st} for CSL and REC.
→ None for RE.
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 15 
An arbitrary Turing machine halts after 100 steps.  
A Turing machine prints a specific letter.  
A Turing machine computes the products of two numbers.  
None of the above.  
Both (B) and (C). 
Question 15 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.
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 15 questions to complete.