1
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following problems is un-decidable?
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.
2
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6
Which of the following is/are undecidable?
$$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$
$$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$
$$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
3
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of the following is TRUE?
A
$${P_3}$$ is decidable if $${P_1}$$ is reducible to $${P_3}$$
B
$${P_3}$$ is in-decidable if $${P_3}$$ is reducible to $${P_2}$$
C
$${P_3}$$ is un-decidable if $${P_2}$$ is reducible to $${P_3}$$
D
$${P_3}$$ is decidable if $${P_3}$$ is reducible to $${P_2}'s$$ complement
4
GATE CSE 2001
MCQ (Single Correct Answer)
+2
-0.6
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,} $$ does the computation of $$M$$ on $$w$$ visit the state $$q''$$

Which of the following statements about $$X$$ is correct?

A
$$X$$ is decidable
B
$$X$$ is undecidable but partially decidable
C
$$X$$ is undecidable and not even partially decidable
D
$$X$$ is not a decision problem
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12