# Undecidability

 Question 1
Consider the following sets:

S1: Set of all recursively enumerable languages over the alphabet {0, 1}.
S2: Set of all syntactically valid C programs.
S3: Set of all languages over the alphabet {0, 1}.
S4: Set of all non-regular languages over the alphabet {0, 1}.

Which of the above sets are uncountable?
 A S1 and S2 B S3 and S4 C S2 and S3 D S1 and S4
GATE CSE 2019      Undecidability
Question 1 Explanation:
 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 Turning machine M. Which of the following decision problems are undecidable ?

I. Given a regular expression R and a string w, is w$\in$L(R)?
II. Given a context-free grammar G, L(G)=$\phi$?
III. Given a context-free grammar G, is L(G)=$\Sigma$* for some alphabet $\Sigma$?
IV. Given a Turning machine M and a string w, is w$\in$L(M)?
 A I and IV only B II and III only C II, III and IV only D III and IV only
GATE CSE 2017 SET-2      Undecidability
Question 2 Explanation:
 Question 3
Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1)$\cap$L(N2) = $\phi$?
II. Given a CFG G = (N,$\Sigma$,P,S) and a string $x \in\Sigma ^*$, does $x \in$ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = $\phi$?
 A I and IV only B II and III only C III and IV only D II and IV only
GATE CSE 2016 SET-1      Undecidability
Question 3 Explanation:
 Question 4
Which one of the following problems is undecidable?
 A Deciding if a given context-free grammar is ambiguous B Deciding if a given string is generated by a given context-free grammar C Deciding if the language generated by a given context-free grammar is empty D Deciding if the language generated by a given context-free grammar is finite.
GATE CSE 2014 SET-3      Undecidability
Question 4 Explanation:
 Question 5
Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^{*}}$ be the power set of $\Sigma^{*}$ . Which one of the following is TRUE?
 A Both $2^{\Sigma^{*}}$ and $\Sigma^{*}$ are countable B $2^{\Sigma^{*}}$ is countable $\Sigma^{*}$ is uncountable C $2^{\Sigma^{*}}$ is uncountable and $\Sigma^{*}$ is countable D Both $2^{\Sigma^{*}}$ and $\Sigma^{*}$ are uncountable
GATE CSE 2014 SET-3      Undecidability
Question 5 Explanation:
 Question 6
Let $A \leq _{m}B$ denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
 A If $A\leq _{m}B$ and B is recursive then A is recursive B If $A\leq _{m}B$ and A is undecidable then B is undecidable C If $A\leq _{m}B$ and B is recursively enumerable then A is recursively enumerable. D If $A\leq _{m}B$ and B is not recursively enumerable then A is not recursively enumerable
GATE CSE 2014 SET-2      Undecidability
Question 6 Explanation:
 Question 7
Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = $\Phi$?
2. G is a CFG. Is L(G) = $\Sigma ^{*}$ ?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
 A 3 only B 3 and 4 only C 1, 2 and 3 only D 2 and 3 only
GATE CSE 2013      Undecidability
Question 7 Explanation:
 Question 8
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 $\bar{L}$ also context-free?
3) If L is a regular language, then, is $\bar{L}$ also regular?
4) If L is a recursive language, then, is $\bar{L}$ also recursive?
 A 1, 2, 3, 4 B 1,2 C 2,3,4 D 3,4
GATE CSE 2012      Undecidability
Question 8 Explanation:
 Question 9
Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
 A I and II B I and IV C II and III D II and IV
GATE CSE 2008      Undecidability
Question 9 Explanation:
 Question 10
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.
GATE CSE 2007      Undecidability
Question 10 Explanation:
There are 10 questions to complete.