# 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

##### Show Answer

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?

##### Show Answer

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:

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let

##### Show Answer

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

##### Show Answer

Which one of the following problems is undecidable?

##### Show Answer

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.

##### Show Answer

Assuming P ≠ NP, which of the following is TRUE?

##### Show Answer

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?

##### Show Answer

Which of the following pairs have DIFFERENT expressive power?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

##### Show Answer

Which of the following problems is undecidable?