GATE CSE 2013 | Undecidability Question 6 | Theory of Computation

GATE CSE 2013

MCQ (Single Correct Answer)

-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)?$$

$$3$$ only

$$3$$ and $$4$$ only

$$1,2$$ and $$3$$ only

$$2$$ and $$3$$ only

GATE CSE 2005

MCQ (Single Correct Answer)

-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?

$${P_3}$$ is decidable if $${P_1}$$ is reducible to $${P_3}$$

$${P_3}$$ is in-decidable if $${P_3}$$ is reducible to $${P_2}$$

$${P_3}$$ is un-decidable if $${P_2}$$ is reducible to $${P_3}$$

$${P_3}$$ is decidable if $${P_3}$$ is reducible to $${P_2}'s$$ complement

GATE CSE 2001

MCQ (Single Correct Answer)

-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?

$$X$$ is decidable

$$X$$ is undecidable but partially decidable

$$X$$ is undecidable and not even partially decidable

$$X$$ is not a decision problem

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Consider the following decision problems :

$${P_1}$$ Does a given finite state machine accept a given string

$${P_2}$$ Does a given context free grammar generate an infinite number of stings.

Which of the following statements is true?

Both $${P_1}$$ and $${P_2}$$ are decidable

Neither $${P_1}$$ and $${P_2}$$ are decidable

Only $${P_1}$$ is decidable

Only $${P_2}$$ is decidable

PREVIOUS NEXT