My Cart
Your Cart 0

    Your cart is empty.

  • Total (Amount) ₹0.00
Previous year question hub

Turing Machines and Undecidability - Theory of Computation - Computer Science & Information Technology Previous Year Questions

Practice Turing Machines and Undecidability - Theory of Computation - Computer Science & Information Technology previous year questions organised from real papers, with year-wise coverage and clear topic navigation.

20Papers
14Years
32Questions
1Topics

Turing Machines and Undecidability question pattern

Every graph below is calculated only from this selection.

Questions by year

Compare question counts across years.

Difficulty distribution

How the classified questions are distributed by difficulty.

Medium 28 87.5%
Easy 4 12.5%

Question type distribution

MCQ, numerical, multiple-select and other formats found in these papers.

MCQ 30 93.8%
Numerical Answer Type (NAT) 1 3.1%
MSQ 1 3.1%

Subject weightage

Top subjects by unique question coverage.

Computer Science & Information Technology
32 Qs

Most asked topics

Top topics across the included previous year papers.

Theory of Computation
32 Qs

Subtopic coverage

Top subtopics inside this exact selection.

Turing Machines and Undecidability
32 Qs

Paper coverage

Question coverage for the most populated papers. Every active PYP paper remains listed below.

Computer Science and Information Technology (CS) 2026
1 Qs
Computer Science & Information Technology (CS) 2022 [Session 2]
1 Qs
Computer Science & Information Technology (CS) 2021 [Session 1]
2 Qs
Computer Science & Information Technology (CS) 2020 [Session 2]
1 Qs
Computer Science & Information Technology (CS) 2019 [Session 2]
1 Qs
Computer Science & Information Technology (CS) 2018 [Session 2]
3 Qs
Computer Science & Information Technology (CS) 2017 [Session 2]
1 Qs
Computer Science & Information Technology (CS) 2016 [Session 1]
2 Qs
Computer Science & Information Technology (CS) 2016 [Session 2]
2 Qs
Computer Science & Information Technology (CS) 2014 [Session 2]
2 Qs
Computer Science & Information Technology (CS) 2014 [Session 3]
2 Qs
Computer Science & Information Technology (CS) 2014 [Session 1]
1 Qs
Computer Science & Information Technology (CS) 2013 [Session 1]
2 Qs
Computer Science & Information Technology (CS) 2013 [Session 3]
2 Qs
Computer Science & Information Technology (CS) 2013 [Session 4]
2 Qs
Computer Science & Information Technology (CS) 2013 [Session 2]
1 Qs
Computer Science & Information Technology (CS) 2010
1 Qs
Computer Science & Information Technology (CS) 2009
1 Qs
Computer Science & Information Technology (CS) 2008
3 Qs
Computer Science & Information Technology (CS) 2007
1 Qs

Included previous year papers

Newest papers appear first. Search these papers or sort by year and name.

Paper nameYearPDFAttempt
Computer Science and Information Technology (CS) 20262026
1 questions in this view		2026
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download Official answer keyOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2022 [Session 2]2022
1 questions in this view		2022
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download Official answer keyOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2021 [Session 1]2021
2 questions in this view		2021
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download Official answer keyOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2020 [Session 2]2020
1 questions in this view		2020
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2019 [Session 2]2019
1 questions in this view		2019
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2018 [Session 2]2018
3 questions in this view		2018
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2017 [Session 2]2017
1 questions in this view		2017
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2016 [Session 1]2016
2 questions in this view		2016
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2016 [Session 2]2016
2 questions in this view		2016
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2014 [Session 1]2014
1 questions in this view		2014
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2014 [Session 2]2014
2 questions in this view		2014
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2014 [Session 3]2014
2 questions in this view		2014
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2013 [Session 1]2013
2 questions in this view		2013
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2013 [Session 2]2013
1 questions in this view		2013
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2013 [Session 3]2013
2 questions in this view		2013
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 2013 [Session 4]2013
2 questions in this view		2013
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 20102010
1 questions in this view		2010
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 20092009
1 questions in this view		2009
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 20082008
3 questions in this view		2008
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download
Computer Science & Information Technology (CS) 20072007
1 questions in this view		2007
ExamElite PDFs
ExamElite solutions
Official documents
Official question paperOriginal authority-issued PDF Official Download

All Turing Machines and Undecidability previous year questions

Practice every matching question in batches of 20, with every available option.

1
2007 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2007

Which of the following problems is undecidable?

Open complete paper
2
2008 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2008
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
Open complete paper
3
2008 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2008
If L and \(\bar{L}\) are recursively enumerable then L is
Open complete paper
4
2008 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2008

Which of the following statements is false?

Open complete paper
5
2009 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2009
Let \(\pi_A\) be a problem that belongs to the class NP. Then which one of the following is TRUE ?
Open complete paper
6
2010 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2010

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Open complete paper
7
2013 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2013 [Session 1]
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.
Open complete paper
8
2013 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2013 [Session 1]
Which of the following is/are undecidable?
1. G is a CFG. Is L(G)=Φ?
2. G is a CFG. Is L(G)=Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A)=L(N)?
Open complete paper
9
2013 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2013 [Session 3]
Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Open complete paper
10
2014 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2014 [Session 1]
Let \(L\) be a language and \(\bar{L}\) be its complement. Which one of the following is NOT a viable possibility?
Open complete paper
11
2014 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2014 [Session 2]
Let \(A \leq_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?
Open complete paper
12
2014 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2014 [Session 2]
Let < M > be the encoding of a Turing machine as a string over Σ = {0,1}. Let L = { < M > | M is a Turing machine that accepts a string of length 2014 }. Then, L is
Open complete paper
13
2014 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2014 [Session 3]
Which one of the following problems is undecidable?
Open complete paper
14
2014 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2014 [Session 3]
Consider the decision problem \(2CNFSAT\) defined as follows:
\(\{ \Phi \mid \Phi\) is a satisfiable propositional formula in CNF with at most two literals per clause \(\}\)
For example, \(\Phi = (x_1 \vee x_2) \wedge (x_1 \vee \neg x_3) \wedge (x_2 \vee x_4)\) is a Boolean formula and it is in \(2CNFSAT\).
The decision problem \(2CNFSAT\) is
Open complete paper
15
2016 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2016 [Session 1]
Which of the following decision problems are undecidable?
I. Given NFAs \(N_1\) and \(N_2\), is \(L(N_1) \cap L(N_2) = \Phi\)?
II. Given a CFG \(G = (N, \Sigma, P, S)\) and a string \(x \in \Sigma^*\), does \(x \in L(G)\)?
III. Given CFGs \(G_1\) and \(G_2\), is \(L(G_1) = L(G_2)\)?
IV. Given a TM \(M\), is \(L(M) = \Phi\)?
Open complete paper
16
2016 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2016 [Session 1]
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 \(Y\) reduces to \(W\), and \(Z\) reduces to \(X\) (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
Open complete paper
17
2017 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2017 [Session 2]
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 \( M \). Which of the following decision problems are undecidable?
I. Given a regular expression \( R \) and a string \( w \), is \( w \in L(R) \)?
II. Given a context-free grammar \( G \), is \( L(G) = \emptyset \)?
III. Given a context-free grammar \( G \), is \( L(G) = \Sigma^* \) for some alphabet \( \Sigma \)?
IV. Given a Turing machine \( M \) and a string \( w \), is \( w \in L(M) \)?
Open complete paper
18
2018 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2018 [Session 2]

The set of all recursively enumerable languages is

Open complete paper
19
2018 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2018 [Session 2]
Consider the first-order logic sentence \(\varphi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y \; \psi(s, t, u, v, w, x, y)\) where \(\psi(s, t, u, v, w, x, y)\) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose \(\varphi\) has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
Open complete paper
20
2018 · Computer Science & Information Technology · Theory of Computation · Turing Machines and Undecidability
Computer Science & Information Technology (CS) 2018 [Session 2]
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 \(w \in L(G)\)
(II) Given a Turing machine \(M\), whether \(L(M)\) is regular
(III) Given two grammars \(G_1\) and \(G_2\), whether \(L(G_1) = L(G_2)\)
(IV) Given an NFA \(N\), whether there is a deterministic PDA \(P\) such that \(N\) and \(P\) accept the same language.
Which one of the following statements is correct?
Open complete paper

Showing 20 of 26 questions