Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
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
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization