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 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\inL(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 3
Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1)\capL(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 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 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


There are 5 questions to complete.

Leave a Comment