Recursively Enumerable Language and Turing Machine · Theory of Computation · GATE CSE

Which of the following statements is/are TRUE?

Consider the language L = { $${a^n}|n \ge 0$$ } $$ \cup $$ { $${a^n}{b^n}|n \ge 0$$ } and the following statements. I. L is deterministic context-free...

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which...

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessa...

Consider the following statements. $$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing 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...

Which of the following statements is/are FALSE? $$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing mac...

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

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is...

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

Regarding the power of recognition of languages, which of the following statement is false?

Which of the following statements is / are true / false? Regular languages are closed under infinite union.

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

Which of the following statements is / are true / false? The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$...

Which of the following is/are undecidable?

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

The set of all recursively enumerable languages is

Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the language accepted by a machine $$M.$...

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

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

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

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

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

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \left\{ {s \in {{\left( {0 + 1} \r...

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, lan...

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?

A single tape Turing Machine $$M$$ has two states $${q_0}$$ and $${q_1}$$, of which $${q_0}$$ is the starting state. The tape alphabet of $$M$$ is $$\...

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

Which of the following is true?

The $$C$$ language is:

Which one of the following is not decidable?

Which of the following conversions is not possible (algorithmically)?

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

Recursive languages are: