DecidabilityandUndecidability
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 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?
(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 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.
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 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)?
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 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.
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 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 and G_{2}, is L(G_{1}) = L(G_{2})?
IV. Given a TM M, is L(M) = Φ?
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 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 3 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 4 
Consider the following statements:

I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are True?
Only II  
Only III  
Only I and II  
Only I and III 
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.
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 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 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.
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 
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a contextfree language, then, is also contextfree?
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 
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 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 7 
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 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 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.
There are 7 questions to complete.