# GATE Questions & Answers of Turing machines and Undecidability

## What is the Weightage of Turing machines and Undecidability in GATE Exam?

Total 19 Questions have been asked from Turing machines and Undecidability topic of Theory of Computation subject in previous GATE papers. Average marks 1.37.

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.

(I) For an unrestricted grammar G and a string w, whether $\style{font-family:'Times New Roman'}{w\in L(G)}$
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars G1 and G2, whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA such that N and P accept the same language.

Which one of the following statements is correct?

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language $\{x\;\#\;f(x)\vert x\in A^\ast\}$. Which of the following statemeant is true:

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 Turning machine M.

Which of the following decision problems are undecidable?

I. Given a regular expression R and a string $w$, is $\style{font-family:'Times New Roman'}{w\in L(R)}$ ?

II. Given context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}\phi$ ?

III. Given a context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}{\sum\nolimits^\ast}$ for some alphabet $\style{font-family:'Times New Roman'}\sum$ ?

IV. Given a Turning machine M and a string $w$, is $\style{font-family:'Times New Roman'}{w\in L(M)}$ ?

Consider the following languages.
$L_1{=\left\{<M>\vert M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{some}\;\mathrm{input}\right\},}$
$L_2{=\left\{<M>\vert M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{all}\;\mathrm{some}\;\mathrm{inputs}\right\}\mathrm{and}}$
$L_3=\left\{<M>\vert M\;accepts\;\varepsilon\right\}$,
where for each Turing machine $M,<M>$ denotes a specific encoding of $M$. Which one of the following is TRUE?

Consider the following statements.

I.   The complement of every Turing decidable language is Turing decidable
II.  There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

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

Let Am 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 ∑ = {0, 1}. Let

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

Which one of the following problems is undecidable?

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 complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.

Assuming P ≠ NP, which 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 $\stackrel{-}{L}$ also context-free? 3) If $L$ is a regular language, then, is $\stackrel{-}{L}$ also regular? 4) If $L$ is a recursive language, then, is $\stackrel{-}{L}$ also recursive?

Which of the following pairs have DIFFERENT expressive power?

Which of the following is true for the language {ap | p is a prime}?

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

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