What are common examiner traps in Turing Machines and Undecidability?

Assuming Rice's Theorem applies to properties of the machine execution itself (e.g., 'M executes at least 2000 steps') rather than the language L(M) recognized. Reversing the direction of reduction: given A m B, knowing A is decidable/RE tells nothing about B, and knowing B is undecidable/not RE tells nothing about A. Confusing Context-Free Language closure under complementation (CFLs are NOT closed under complement, but the complement of a CFL is always recursive/decidable). Assuming that because a problem is undecidable, it cannot be Recursively Enumerable (forgetting semi-decidability via dovetailed simulation). Confusing L(G) = (decidable for CFGs) with L(G) = * (undecidable for CFGs). Confusing the set of strings * (countably infinite) with the set of languages 2 * (uncountably infinite). Assuming * is finite because is finite. Assuming 2 * is countable because it is constructed over a finite alphabet . Assuming CFLs are closed under intersection by analogy to regular or recursive languages (e.g. confusing context-free with deterministic context-free or regular). Confusing the intersection of two CFLs with the intersection of a CFL and a regular language (which is context-free).

Turing Machines and Undecidability

30 Qs · since 2012 · 44 marks · 1.7 marks/paperMedium yield

Take topic test

Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Questions primarily assess langu… Guide

Type

GATE CSE 2026 Set 2Q13MCQ1 markEasyWhich one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq \{0,1\}^*$
GATE CSE 2025 Set 2Q25MCQ1 markEasyLet $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?
GATE CSE 2023Q24MSQ1 markEasyWhich of the following statements is/are CORRECT?
GATE CSE 2022Q23MSQ1 markMediumWhich of the following statements is/are TRUE?
GATE CSE 2022Q46MSQ2 marksMediumWhich of the following is/are undecidable?
GATE CSE 2021 Set 1Q12MSQ1 markMediumLet $\langle M \rangle$ denote an encoding of an automaton $M$ . Suppose that $\Sigma = \{0, 1\}$ . Which of the following languages is/are NOT recursive?
GATE CSE 2021 Set 1Q39MCQ2 marksMediumFor a Turing machine $M$ , $\langle M \rangle$ denotes an encoding of $M$ . Consider the following two languages. $L_1 = \{\langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs}\}$ $L_2 = \{\langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on some input}\}$ Which…
GATE CSE 2021 Set 2Q36MCQ2 marksMediumConsider 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 choices is correct?
GATE CSE 2020Q26MCQ2 marksMediumWhich of the following languages are undecidable? Note that $\langle M \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\langle M \rangle \mid L(M) = \emptyset\}$ $L_2 = \{\langle M, w, q \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly 100 steps}\}$ $L_3 = \{\langle M \rangle \mid L(M) \text{ is not recursive}\}$ …
GATE CSE 2018Q7MCQ1 markEasyThe set of all recursively enumerable languages is
GATE CSE 2017 Set 1Q39MCQ2 marksMediumLet $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 $L_f$ denote the…
GATE CSE 2017 Set 2Q41MCQ2 marksMediumLet $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…
GATE CSE 2016 Set 1Q17MCQ1 markEasyWhich 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$ …
GATE CSE 2016 Set 1Q44MCQ2 marksMediumLet $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}$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
GATE CSE 2016 Set 2Q18MCQ1 markMediumConsider 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? I. $\overline{L_3} \cup L_4$ is recursively enumerable II. $\overline{L_2} \cup L_3$ is recursive III. $L_1^* \cap L_2$ is context-free…
GATE CSE 2016 Set 2Q44MCQ2 marksMediumConsider the following languages. $\begin{aligned} L_1 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on some input}\}, L_2 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on all inputs}\} \text{ and} L_3 &= \{\langle M \rangle \mid M \text{ accepts } \varepsilon\}, \end{aligned}$ …
GATE CSE 2015 Set 1Q3MCQ1 markMediumFor 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. $\bar{L}_1$ (complement of $L_1$ ) is recursive II. $\bar{L}_2$ (complement of $L_2$ ) is recursive III. $\bar{L}_1$ is…
GATE CSE 2015 Set 2Q2MCQ1 markMediumConsider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$ . Then which one of the following is consistent with the above statement?
GATE CSE 2015 Set 2Q21MCQ1 markMediumConsider 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?
GATE CSE 2015 Set 3Q53MCQ2 marksMediumLanguage $L_1$ is polynomial time reducible to language $L_2$ . Language $L_3$ is polynomial time reducible to $L_2$ , which in turn is polynomial time reducible to language $L_4$ . Which of the following is/are true? I. if $L_4 \in P$ , then $L_2 \in P$ II. if $L_1 \in P$ or $L_3 \in P$ , then $L_2 \in P$ …
GATE CSE 2014 Set 1Q35MCQ2 marksEasyLet $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility?
GATE CSE 2014 Set 1Q38MCQ2 marksMediumSuppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
GATE CSE 2014 Set 2Q16MCQ1 markMediumLet $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?
GATE CSE 2014 Set 2Q35MCQ2 marksMediumLet $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma = \{0,1\}$ . Let $L = \{\langle M \rangle \mid M\text{ is a Turing machine that accepts a string of length 2014}\}$ . Then, $L$ is
GATE CSE 2014 Set 3Q16MCQ1 markEasyLet $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$ . Which one of the following is TRUE?
GATE CSE 2014 Set 3Q35MCQ2 marksEasyWhich one of the following problems is undecidable?
GATE CSE 2013Q17MCQ1 markEasyWhich 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.…
GATE CSE 2013Q41MCQ2 marksEasyWhich of the following is/are undecidable? 1. $G$ is a CFG. Is $L(G) = \Phi$ ? 2. $G$ is a CFG. Is $L(G) = \Sigma^*$ ? 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)$ ?
GATE CSE 2012Q4MCQ1 markEasyAssuming $\text{P} \neq \text{NP}$ , which of the following is $\textbf{TRUE}$ ?
GATE CSE 2012Q24MCQ1 markMediumWhich 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, then, is $\overline{L}$ also regular? 4) If $L$ is a recursive language, then, is $\overline{L}$ …

Topic guide

What does GATE test in Turing Machines and Undecidability?

Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Questions primarily assess language hierarchies (Recursive vs. Recursively Enumerable), closure properties under complement and set operations, mapping reductions ( $A \le_m B$ ), and Rice's Theorem applied to TM behavior. A frequent focus is distinguishing semantic properties of languages (undecidable) from finite-step or prefix-bounded properties of machine computations (decidable).

Core concepts

Rice's Theorem (semantic/non-trivial properties of RE languages vs syntactic/step-bounded properties)
Post's Theorem and complementation of RE / REC languages
Many-to-one (mapping) reduction (A m B) and its directional properties
Polynomial-time reduction (A p B) and NP-completeness foundations
Decidability hierarchy: Regular (all standard decision problems decidable), CFL (emptiness, finiteness, membership decidable; universality, equivalence, ambiguity undecidable), TM (almost all semantic problems undecidable)
Deterministic vs. Non-Deterministic Turing Machine equivalence
Countable set of TMs vs. Uncountable set of languages (subset cardinality arguments)
Formal definition of deciders vs recognizers (halting on all inputs)
Countability of * (set of all finite strings)
Uncountability of 2 * (power set of all strings / set of all languages)
Application of Cantor's theorem to formal languages
Lexicographical ordering of finite strings
Closure properties of Regular languages
Closure properties of Context-Free languages (CFLs)
Closure properties of Recursive (Decidable) languages
Closure properties of Recursively Enumerable (Turing-recognizable) languages
Non-closure of CFLs under intersection

Recurring question patterns

Rice's Theorem and Semantic Properties vs. Step-Bounded Behavior
common · MCQ · 2 marks · 2022, 2021, 2020, 2016
Determining whether a language encoding TM properties (e.g., $L = \{\langle M \rangle \mid P(L(M))\}$ ) is decidable or undecidable. Tests understanding that non-trivial semantic properties of $L(M)$ are undecidable by Rice's Theorem, whereas properties bounding the number of execution steps (e.g., 'takes more than $k$ steps') or finite tape head prefixes are decidable by bounded simulation.
Chomsky Hierarchy Decidability and Decision Properties Matrix
common · MCQ · 1 marks · 2025, 2021, 2017, 2016
Evaluating the decidability of classical decision problems (emptiness, universality, membership, equivalence, ambiguity, regularity) across Regular, Context-Free, and Turing-recognizable languages.
Mapping Reductions and Computability Propagation
common · MCQ · 2 marks · 2016, 2015, 2014
Analyzing implications of mapping reducibility ( $A \le_m B$ or $A \le_p B$ ) regarding decidability, recursive enumerability, and complexity classes (P, NP, NP-complete, NP-hard). Focuses on contrapositive arguments and directional inference.
Complement and Post's Theorem Combinations
common · mixed · 1 marks · 2022, 2018, 2016, 2015
Questions evaluating the relationship between a language $L$ and its complement $\overline{L}$ (e.g., $L \in \text{REC} \iff L \in \text{RE} \land \overline{L} \in \text{RE}$ , or unions/intersections of different classes in the hierarchy).
Fundamental Definitions and Cardinality / Set-Theoretic Arguments
occasional · mixed · 1 marks · 2026, 2022, 2021, 2018
Testing core formal definitions of Turing machines (deciding vs. recognizing), countability of Turing machines vs. uncountability of languages, and existence of undecidable subsets within infinite regular languages.
Cardinality and Countability of Strings vs Languages
rare · MCQ · 1 marks · 2014
Determining whether string universes ( $\Sigma^*$ ) and language sets ( $2^{\Sigma^*}$ ) or specific language classes are countable or uncountable.
Closure Property Evaluation across Chomsky Hierarchy
common · MSQ · 1 marks · 2023
A set of theoretical assertions asking which closure properties hold for different classes of formal languages (Regular, CFL, Recursive, RE) under set-theoretic operations.

Formulas GATE uses

Post's Theorem

L \in \text{REC} \iff (L \in \text{RE}) \land (\overline{L} \in \text{RE})

Used when analyzing the decidability of $L$ given the enumerability of $L$ and $\overline{L}$ .

Mapping Reduction Decidability Transfer

A \le_m B \land B \in \text{REC} \implies A \in \text{REC}

Used when deducing the recursiveness or undecidability of languages under many-one reductions.

Mapping Reduction RE Transfer

A \le_m B \land B \in \text{RE} \implies A \in \text{RE}

Used when determining semi-decidability transfer or its contrapositive ( $A \notin \text{RE} \implies B \notin \text{RE}$ ).

Polynomial Reduction P Transfer

L_1 \le_p L_2 \land L_2 \in \text{P} \implies L_1 \in \text{P}

Used in complexity class questions involving reductions among problems in P, NP, and NP-hard.

Graph of a Computable Function

L_f = \{x\#f(x) \mid x \in \Sigma^*\} \in \text{REC} \iff f \text{ is total computable}

Used when relating functional computability of $f$ to language decidability of its encoding.

Cardinality of String Universe $\Sigma^*$

|\Sigma^*| = \aleph_0

Used to establish that the set of all finite strings over a finite alphabet is countably infinite via standard lexicographical enumeration.

Cantor's Theorem for Language Universe

|2^{\Sigma^*}| = 2^{\aleph_0} = \mathfrak{c} > \aleph_0

Used to prove that the set of all possible languages over $\Sigma$ is uncountably infinite.

De Morgan's Law for Regular Languages

L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}

Proving closure of regular languages under intersection using closure under complementation and union.

Examiner traps in Turing Machines and Undecidability

Assuming Rice's Theorem applies to properties of the machine execution itself (e.g., 'M executes at least 2000 steps') rather than the language L(M) recognized.
Reversing the direction of reduction: given A m B, knowing A is decidable/RE tells nothing about B, and knowing B is undecidable/not RE tells nothing about A.
Confusing Context-Free Language closure under complementation (CFLs are NOT closed under complement, but the complement of a CFL is always recursive/decidable).
Assuming that because a problem is undecidable, it cannot be Recursively Enumerable (forgetting semi-decidability via dovetailed simulation).
Confusing L(G) = (decidable for CFGs) with L(G) = * (undecidable for CFGs).
Confusing the set of strings * (countably infinite) with the set of languages 2 * (uncountably infinite).
Assuming * is finite because is finite.
Assuming 2 * is countable because it is constructed over a finite alphabet .
Assuming CFLs are closed under intersection by analogy to regular or recursive languages (e.g. confusing context-free with deterministic context-free or regular).
Confusing the intersection of two CFLs with the intersection of a CFL and a regular language (which is context-free).

How questions are asked

Multi-statement true/false evaluation across closure and decidability properties
Classification of TM property languages into decidable, RE but undecidable, or not RE
Identification of decidable vs undecidable problems from a listed set of classical decision questions
Mapping reduction implication checks (A m B / P p Q)
MSQ selection of all true computability assertions
Direct conceptual multiple-choice question on countability properties
Identify correct/incorrect statements regarding closure properties across language classes (MSQ/MCQ).

Paper trends

Introduction of step-bounded TM decision problems (e.g., simulating $M$ for $k$ steps on inputs of bounded length) as a recurring counter-example to Rice's Theorem.
2022, 2021, 2020, 2016
Adoption of MSQ format to test multiple distinct decidability and closure assertions simultaneously without negative marking.
2022, 2021
Heavy reliance on standard decision problem tables (emptiness, universality, equivalence) across grammar classes (CFG vs Regular vs TM).
2025, 2017, 2016, 2014, 2013, 2012
Appeared as a direct, 1-mark foundational conceptual question testing basic definitions of countable vs uncountable infinite sets in automata theory.
2014
Testing conceptual closure properties via Multiple Select Questions (MSQ) where each option corresponds to a distinct formal language class under the same operation.
2023

Difficulty notes

Easy questions directly recall closure properties or standard entries in the decidability table (e.g., emptiness of CFG vs TM, definition of TM decider). Medium questions involve reasoning through many-one reductions with complementation, dovetailed simulation arguments to separate RE from non-RE, or identifying step-bounded deciders that bypass Rice's Theorem.

Turing Machines and Undecidability

30 Qs · since 2012 · 44 marks · 1.7 marks/paperMedium yield

Take topic test

Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Questions primarily assess langu… Guide

Type

Topic guide

What does GATE test in Turing Machines and Undecidability?

Core concepts

Rice's Theorem (semantic/non-trivial properties of RE languages vs syntactic/step-bounded properties)
Post's Theorem and complementation of RE / REC languages
Many-to-one (mapping) reduction (A m B) and its directional properties
Polynomial-time reduction (A p B) and NP-completeness foundations
Decidability hierarchy: Regular (all standard decision problems decidable), CFL (emptiness, finiteness, membership decidable; universality, equivalence, ambiguity undecidable), TM (almost all semantic problems undecidable)
Deterministic vs. Non-Deterministic Turing Machine equivalence
Countable set of TMs vs. Uncountable set of languages (subset cardinality arguments)
Formal definition of deciders vs recognizers (halting on all inputs)
Countability of * (set of all finite strings)
Uncountability of 2 * (power set of all strings / set of all languages)
Application of Cantor's theorem to formal languages
Lexicographical ordering of finite strings
Closure properties of Regular languages
Closure properties of Context-Free languages (CFLs)
Closure properties of Recursive (Decidable) languages
Closure properties of Recursively Enumerable (Turing-recognizable) languages
Non-closure of CFLs under intersection

Recurring question patterns

Rice's Theorem and Semantic Properties vs. Step-Bounded Behavior
common · MCQ · 2 marks · 2022, 2021, 2020, 2016
Determining whether a language encoding TM properties (e.g., $L = \{\langle M \rangle \mid P(L(M))\}$ ) is decidable or undecidable. Tests understanding that non-trivial semantic properties of $L(M)$ are undecidable by Rice's Theorem, whereas properties bounding the number of execution steps (e.g., 'takes more than $k$ steps') or finite tape head prefixes are decidable by bounded simulation.
Chomsky Hierarchy Decidability and Decision Properties Matrix
common · MCQ · 1 marks · 2025, 2021, 2017, 2016
Evaluating the decidability of classical decision problems (emptiness, universality, membership, equivalence, ambiguity, regularity) across Regular, Context-Free, and Turing-recognizable languages.
Mapping Reductions and Computability Propagation
common · MCQ · 2 marks · 2016, 2015, 2014
Analyzing implications of mapping reducibility ( $A \le_m B$ or $A \le_p B$ ) regarding decidability, recursive enumerability, and complexity classes (P, NP, NP-complete, NP-hard). Focuses on contrapositive arguments and directional inference.
Complement and Post's Theorem Combinations
common · mixed · 1 marks · 2022, 2018, 2016, 2015
Questions evaluating the relationship between a language $L$ and its complement $\overline{L}$ (e.g., $L \in \text{REC} \iff L \in \text{RE} \land \overline{L} \in \text{RE}$ , or unions/intersections of different classes in the hierarchy).
Fundamental Definitions and Cardinality / Set-Theoretic Arguments
occasional · mixed · 1 marks · 2026, 2022, 2021, 2018
Testing core formal definitions of Turing machines (deciding vs. recognizing), countability of Turing machines vs. uncountability of languages, and existence of undecidable subsets within infinite regular languages.
Cardinality and Countability of Strings vs Languages
rare · MCQ · 1 marks · 2014
Determining whether string universes ( $\Sigma^*$ ) and language sets ( $2^{\Sigma^*}$ ) or specific language classes are countable or uncountable.
Closure Property Evaluation across Chomsky Hierarchy
common · MSQ · 1 marks · 2023
A set of theoretical assertions asking which closure properties hold for different classes of formal languages (Regular, CFL, Recursive, RE) under set-theoretic operations.

Formulas GATE uses

Post's Theorem

L \in \text{REC} \iff (L \in \text{RE}) \land (\overline{L} \in \text{RE})

Used when analyzing the decidability of $L$ given the enumerability of $L$ and $\overline{L}$ .

Mapping Reduction Decidability Transfer

A \le_m B \land B \in \text{REC} \implies A \in \text{REC}

Used when deducing the recursiveness or undecidability of languages under many-one reductions.

Mapping Reduction RE Transfer

A \le_m B \land B \in \text{RE} \implies A \in \text{RE}

Used when determining semi-decidability transfer or its contrapositive ( $A \notin \text{RE} \implies B \notin \text{RE}$ ).

Polynomial Reduction P Transfer

L_1 \le_p L_2 \land L_2 \in \text{P} \implies L_1 \in \text{P}

Used in complexity class questions involving reductions among problems in P, NP, and NP-hard.

Graph of a Computable Function

L_f = \{x\#f(x) \mid x \in \Sigma^*\} \in \text{REC} \iff f \text{ is total computable}

Used when relating functional computability of $f$ to language decidability of its encoding.

Cardinality of String Universe $\Sigma^*$

|\Sigma^*| = \aleph_0

Used to establish that the set of all finite strings over a finite alphabet is countably infinite via standard lexicographical enumeration.

Cantor's Theorem for Language Universe

|2^{\Sigma^*}| = 2^{\aleph_0} = \mathfrak{c} > \aleph_0

Used to prove that the set of all possible languages over $\Sigma$ is uncountably infinite.

De Morgan's Law for Regular Languages

L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}

Proving closure of regular languages under intersection using closure under complementation and union.

Examiner traps in Turing Machines and Undecidability

Assuming Rice's Theorem applies to properties of the machine execution itself (e.g., 'M executes at least 2000 steps') rather than the language L(M) recognized.
Reversing the direction of reduction: given A m B, knowing A is decidable/RE tells nothing about B, and knowing B is undecidable/not RE tells nothing about A.
Confusing Context-Free Language closure under complementation (CFLs are NOT closed under complement, but the complement of a CFL is always recursive/decidable).
Assuming that because a problem is undecidable, it cannot be Recursively Enumerable (forgetting semi-decidability via dovetailed simulation).
Confusing L(G) = (decidable for CFGs) with L(G) = * (undecidable for CFGs).
Confusing the set of strings * (countably infinite) with the set of languages 2 * (uncountably infinite).
Assuming * is finite because is finite.
Assuming 2 * is countable because it is constructed over a finite alphabet .
Assuming CFLs are closed under intersection by analogy to regular or recursive languages (e.g. confusing context-free with deterministic context-free or regular).
Confusing the intersection of two CFLs with the intersection of a CFL and a regular language (which is context-free).

How questions are asked

Multi-statement true/false evaluation across closure and decidability properties
Classification of TM property languages into decidable, RE but undecidable, or not RE
Identification of decidable vs undecidable problems from a listed set of classical decision questions
Mapping reduction implication checks (A m B / P p Q)
MSQ selection of all true computability assertions
Direct conceptual multiple-choice question on countability properties
Identify correct/incorrect statements regarding closure properties across language classes (MSQ/MCQ).

Paper trends

Introduction of step-bounded TM decision problems (e.g., simulating $M$ for $k$ steps on inputs of bounded length) as a recurring counter-example to Rice's Theorem.
2022, 2021, 2020, 2016
Adoption of MSQ format to test multiple distinct decidability and closure assertions simultaneously without negative marking.
2022, 2021
Heavy reliance on standard decision problem tables (emptiness, universality, equivalence) across grammar classes (CFG vs Regular vs TM).
2025, 2017, 2016, 2014, 2013, 2012
Appeared as a direct, 1-mark foundational conceptual question testing basic definitions of countable vs uncountable infinite sets in automata theory.
2014
Testing conceptual closure properties via Multiple Select Questions (MSQ) where each option corresponds to a distinct formal language class under the same operation.
2023