Undecidability · Theory of Computation · GATE CSE

Which of the following decision problems are undecidable?

$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right) \cap L\left( {{N_2}} \right) = \Phi ?$$
$$\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$Given a $$CFG\,G = \left( {N,\sum {\,,P} ,S} \right)$$ and string $$x \in \sum {^ * } ,$$ does
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$x \in L\left( G \right)?$$
$$\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$CFGs\,\,{G_1}$$ and $${G_2},$$ is $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)?$$
$$\,\,\,\,\,\,{\rm I}V.\,\,\,\,\,\,\,\,\,\,$$ Given a $$TM$$ $$M,$$ is $$L\left( M \right) = \Phi ?$$

Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the following is TRUE?

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 $$\overline L $$ also context-free?
$$3.$$ If L is a regular language, then, is $$\overline L $$ also regular?
$$4.$$ If L is a recursive language, then, is $$\overline L $$ also recursive?

Which of the following are decidable?
$$1.$$ Whether the intersection of two regular languages is infinite
$$2.$$ Whether a given context-free language is regular
$$3.$$ Whether two push-down automata accept the same language
$$4.$$ Whether a given grammar is context-free

Which of the following statements is false?

Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M.

L₁ = $$\left\{ {\langle M\rangle |L\left( M \right) = \phi } \right\}$$
L₂ = $$\{ \langle M,w,q\rangle |$$ M on input w reaches state q in exactly 100 steps }
L₃ = { $$\langle M\rangle |$$ L(M) is not recursive }
L₄ = { $$\langle M\rangle |$$ L(M) contains at least 21 members }

Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible to $${L_2}$$ , which in turn is polynomial time reducible to language $${L_4}$$ . Which of the following is/are true?

$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P$$ or $$\,\,\,{L_3} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P,$$ and only $$\,\,\,{L_3} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}V.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_1} \in P$$ and $$\,\,\,{L_3} \in P$$

Which one of the following problems is un-decidable?

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

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?

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?

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?

Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$

It is decidable whether:

Which of the following problems are un-decidable?