Turing Machines and Chomsky Hierarchy

Questions

1. GATE CS 2023MSQ1 markEasy (estimate)

   GATE CS 2023, Q.24

   Which of the following statements is/are CORRECT?

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

2. GATE CS 2017 Set 1MCQ2 marksMedium (estimate)

   GATE CS 2017 Set 1, Q.39 (CS Q.39)

   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^{\ast }$ to $B^{\ast }$. We say $f$ is computable if there exists a T...

   Turing Machines and Chomsky Hierarchy

3. GATE CS 2017 Set 2MCQ2 marksMedium (estimate)

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

   Consider the following languages.…

   Context-Free Grammars, Pushdown Automata and CFLs · Turing Machines and Chomsky Hierarchy

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

5. GATE CS 2014 Set 1MCQ2 marksMedium (estimate)

   GATE CS 2014 Set 1, Q.48 (CS Q.38)

   Suppose 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 correc...

   Turing Machines and Chomsky Hierarchy

6. GATE CS 2013MCQ1 markEasy (estimate)

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

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

   Turing Machines and Chomsky Hierarchy

7. GATE CS 2013MCQ1 markEasy (estimate)

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

   Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether ther...

   Turing Machines and Chomsky Hierarchy

Other topics of Theory of Computation

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