Decidability, Reducibility and Undecidability

Questions

1. GATE CS 2026 Set 2MCQ1 markEasy (estimate)

   GATE CS 2026 Set 2, Q.13

   Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L\subseteq \{0,1{\}}^{\ast }$

   Decidability, Reducibility and Undecidability

2. GATE CS 2025 Set 2MCQ1 markEasy (estimate)

   GATE CS 2025 Set 2, Q.25

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

   Decidability, Reducibility and Undecidability

3. GATE CS 2025 Set 2MSQ1 markEasy (estimate)

   GATE CS 2025 Set 2, Q.30

   Consider the two lists List I and List II given below: List I List II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complementa...

   Context-Free Grammars, Pushdown Automata and CFLs · Decidability, Reducibility and Undecidability · Regular Expressions, Finite Automata and Regular Languages

4. GATE CS 2022MSQ1 markMedium (estimate)

   GATE CS 2022, Q.23

   Which of the following statements is/are TRUE?

   Decidability, Reducibility and Undecidability · Context-Free Grammars, Pushdown Automata and CFLs

5. GATE CS 2022MSQ2 marksMedium (estimate)

   GATE CS 2022, Q.46

   Which of the following is/are undecidable?

   Decidability, Reducibility and Undecidability

6. GATE CS 2021 Set 1MSQ1 markMedium (estimate)

   GATE CS 2021 Set 1, Q.22 (CS Q.12)

   Let $⟨M⟩$ denote an encoding of an automaton $M$. Suppose that $\Sigma =\{0,1\}$. Which of the following languages is/are NOT recursive?

   Decidability, Reducibility and Undecidability

7. GATE CS 2021 Set 1MCQ2 marksMedium (estimate)

   GATE CS 2021 Set 1, Q.49 (CS Q.39)

   For a Turing machine $M$, $⟨M⟩$ denotes an encoding of $M$. Consider the following two languages.…

   Decidability, Reducibility and Undecidability

8. GATE CS 2021 Set 2MCQ2 marksMedium (estimate)

   GATE CS 2021 Set 2, Q.46 (CS Q.36)

   Consider 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...

   Decidability, Reducibility and Undecidability

9. GATE CS 2020MCQ2 marksMedium (estimate)

   GATE CS 2020, Q.36 (CS Q.26)

   Which of the following languages are undecidable? Note that $⟨M⟩$ indicates encoding of the Turing machine $M$.…

   Decidability, Reducibility and Undecidability

10. GATE CS 2019MCQ2 marksMedium (estimate)

    GATE CS 2019, Q.44 (CS Q.34)

    Consider the following sets: $S_1$: Set of all recursively enumerable languages over the alphabet $\{0,1\}$ $S_2$: Set of all syntactically valid C programs $S_3$: Set of all l...

    Decidability, Reducibility and Undecidability

11. GATE CS 2018MCQ1 markEasy (estimate)

    GATE CS 2018, Q.17 (CS Q.7)

    The set of all recursively enumerable languages is

    Decidability, Reducibility and Undecidability

12. GATE CS 2018MCQ2 marksMedium (estimate)

    GATE CS 2018, Q.46 (CS Q.36)

    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…

    Decidability, Reducibility and Undecidability

13. GATE CS 2017 Set 2MCQ2 marksEasy (estimate)

    GATE CS 2017 Set 2, Q.41 (CS Q.41)

    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 Tu...

    Decidability, Reducibility and Undecidability

14. GATE CS 2016 Set 1MCQ1 markMedium (estimate)

    GATE CS 2016 Set 1, Q.27 (CS Q.17)

    Which of the following decision problems are undecidable? I. Given NFAs $N_1$ and $N_2$, is $L(N_1)\cap L(N_2)=\varnothing$? II. Given a CFG $G=(N,\Sigma ,P,S)$ and a strin...

    Decidability, Reducibility and Undecidability

15. GATE CS 2016 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2016 Set 1, Q.54 (CS Q.44)

    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 $\overline{Y}$ reduces to $W$, and $Z$...

    Decidability, Reducibility and Undecidability

16. GATE CS 2016 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2016 Set 2, Q.54 (CS Q.44)

    Consider the following languages. $L_1=\{⟨M⟩\mid M\text{ takes at least 2016 steps on some input}\}$…

    Decidability, Reducibility and Undecidability · Turing Machines and Chomsky Hierarchy

17. GATE CS 2015 Set 1MCQ1 markMedium (estimate)

    GATE CS 2015 Set 1, Q.13 (CS Q.3)

    For 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.…

    Decidability, Reducibility and Undecidability

18. GATE CS 2015 Set 2MCQ1 markMedium (estimate)

    GATE CS 2015 Set 2, Q.31 (CS Q.21)

    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 deci...

    Decidability, Reducibility and Undecidability

19. GATE CS 2014 Set 1MCQ2 marksEasy (estimate)

    GATE CS 2014 Set 1, Q.45 (CS Q.35)

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

    Decidability, Reducibility and Undecidability

20. GATE CS 2014 Set 2MCQ1 markMedium (estimate)

    GATE CS 2014 Set 2, Q.26 (CS Q.16)

    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 following is FALSE?

    Decidability, Reducibility and Undecidability

21. GATE CS 2014 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2014 Set 2, Q.45 (CS Q.35)

    Let $⟨M⟩$ be the encoding of a Turing machine as a string over $\Sigma =\{0,1\}$. Let…

    Decidability, Reducibility and Undecidability

22. GATE CS 2014 Set 3MCQ1 markEasy (estimate)

    GATE CS 2014 Set 3, Q.26 (CS Q.16)

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

    Decidability, Reducibility and Undecidability

23. GATE CS 2014 Set 3MCQ2 marksEasy (estimate)

    GATE CS 2014 Set 3, Q.45 (CS Q.35)

    Which one of the following problems is undecidable?

    Decidability, Reducibility and Undecidability

24. GATE CS 2013MCQ2 marksEasy (estimate)

    GATE CS 2013, Q.41 (CS Q.41)

    Which of the following is/are undecidable? 1. $G$ is a CFG. Is $L(G)=\Phi$? 2. $G$ is a CFG. Is $L(G)={\Sigma }^{\ast }$? 3. $M$ is a Turing machine. Is $L(M)$ regular? 4. $A$ is a D...

    Decidability, Reducibility and Undecidability

25. GATE CS 2012MCQ1 markMedium (estimate)

    GATE CS 2012, Q.24 (CS Q.24)

    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 $\overline{L}$ also context-free? 3...

    Decidability, Reducibility and Undecidability · Regular Expressions, Finite Automata and Regular Languages

Other topics of Theory of Computation

• Regular Expressions, Finite Automata and Regular Languages
• Context-Free Grammars, Pushdown Automata and CFLs
• Turing Machines and Chomsky Hierarchy