Turing Machines & Computability

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

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 questions is decidable?

Which of the following statements is/are CORRECT?

Which of the following is/are undecidable?

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 2021 steps on some input} Which one of t...

Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every finite language is regular. Which one of the following choice...

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?

Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M. L 1 = $$\left\{ {\langle M\rangle |L\left( M \right) = \phi } \right\}$$ L 2 = $$\{ \langle M,...

Consider the following sets : S1. Set of all recursively enumerable languages over the alphabet $\{0,1\}$ S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet $\{0,1\}$ S4. Set of all...

Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the language accepted by a machine $$M.$$ $$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ For an unrestricted gramm...

The set of all recursively enumerable languages is

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

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,$$ and $$Z$$ reduces to $$\overline X $$...

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE ? $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,...

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

For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. $${\overline L _1}$$ (complement of L 1 ) is recursi...

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

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 $$ < 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 machine that accepts a string of length $$\lef...

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

Which one of the following problems is un-decidable?

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

Which of the following statements is/are FALSE ? $$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine $$2.$$ Turing recognizable languages are closed under union and...

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

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 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 two push-down automata accept the same lan...

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\}$$?

Which of the following statement is false?

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 following statement is false?

Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one 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 ?

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?

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?

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 > \left| M \right.} \right.$$ does not ha...

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 \,\,\,\,Otherwise} \cr } } \right.$$ Which o...

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

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

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 (vi) non-recursive procedure call (vii)...

$$\sum { = \left\{ {a,b} \right\},\,\,} $$ which one of the following sets is not countable.

Which one of the following is not decidable?

Which of the following statements is false?

Which of the following statements is / are true / false? Union of two recursive languages is recursive

In which of the cases stated below is the following statement true? “For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recognizing the same language“.

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

State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine M accepts input $$w$$ is un-decidable.

Which of the following problems are un-decidable?