Decidability

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

Let G1, G2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is d...

Let $G_1, G_2$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$. Which ONE among the following qu...

Which of the following statements is/are TRUE?

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L 1 = {(M) | M takes more than 2021 steps on all inputs} L 2 = {(M) | M takes more than...

Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

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 Turing machine...

Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y $$ reduces to $$W,$...

Consider the following languages. $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \,...

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right)...

Consider the following statements. $$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable $$\,$$ $${\rm II}.\,\,\,\,\,\,\,\...

Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$ Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machin...

Which one of the following problems is un-decidable?

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

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.$$...

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-fr...

Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following statement is not necessarily tr...

Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

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 tw...

If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, language. Which one of the follow...

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 three decision problems P 1 , P 2 and P 3 . It is known that P 1 is decidable and P 2 is undecidable. Which one of the following is TRUE ?

Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows $$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,...

Define Languages $${L_0}$$ and $${L_1}$$ as follows $${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$ $${L_1} = \left\{ { < M,w,1 >...

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements 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 {^ * ,} $$ do...

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

Given the programming constructs: (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to (v) arbitrary go to...

Which one of the following is not decidable?

Which of the following statements is false?

State whether the following statement is TRUE / FALSE. A is recursive if both a and its complement are accepted by Turing Machine M accepts.

Which of the following problems are un-decidable?