Chomsky hierarchy MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

In the Chomsky hierarchy of formal languages, which class includes all regular languages?

A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: D) Type 3

Which type of grammar in the Chomsky hierarchy generates context-free languages?

A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: C) Type 2

True or False: Context-sensitive languages are a proper subset of context-free languages in the Chomsky hierarchy.

A) True
B) False
Answer: B) False

Which type of automaton corresponds to type 3 languages in the Chomsky hierarchy?

A) Turing machine
B) Pushdown automaton
C) Finite automaton
D) Linear-bounded automaton
Answer: C) Finite automaton

What is the defining property of type 1 grammars in the Chomsky hierarchy?

A) They generate regular languages.
B) They generate context-free languages.
C) They generate context-sensitive languages.
D) They generate recursively enumerable languages.
Answer: C) They generate context-sensitive languages.

Which class in the Chomsky hierarchy includes languages that can be decided by a Turing machine?

A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: A) Type 0

In the context of formal languages, what is the primary distinction between type 0 and type 1 languages?

A) Type 0 languages can be recognized by a Turing machine.
B) Type 1 languages are context-free.
C) Type 0 languages are recursively enumerable.
D) Type 1 languages are regular.
Answer: B) Type 1 languages are context-free.

Which type of grammar can generate all recursively enumerable languages in the Chomsky hierarchy?

A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: A) Type 0

Which type of automaton corresponds to type 2 languages in the Chomsky hierarchy?

A) Finite automaton
B) Pushdown automaton
C) Turing machine
D) Linear-bounded automaton
Answer: B) Pushdown automaton

Which theoretical framework did Noam Chomsky propose to classify formal languages based on their generative power?

A) Automata theory
B) Turing machine theory
C) Grammar theory
D) Complexity theory
Answer: C) Grammar theory

 

• Theory of Automata MCQs
• Finite Automata MCQs
  • Deterministic Finite Automata (DFA) MCQs
  • Non-deterministic Finite Automata (NFA) MCQs
  • Equivalence of DFA and NFA MCQs
  • Minimization of DFA MCQs
• Regular Languages
  • Regular Expression MCQs
  • Properties of regular languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for regular languages MCQs
• Context-Free Grammars (CFG)
  • CFG MCQs
  • Parse trees and derivations MCQs
  • Ambiguity in grammars MCQs
• Pushdown Automata (PDA) MCQs
  • Deterministic PDA vs Non-deterministic PDA MCQs
  • Relationship between PDA and context-free languages MCQs
• Context-Free Languages MCQs
  • Properties of context-free languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for context-free languages MCQs
• Turing Machines MCQs
  • Turing machine as a language recognizer and transducer MCQs
• Decidability and Undecidability MCQs
  • Decidable languages and problems MCQs
  • Undecidable languages and problems MCQs
  • Rice’s theorem MCQs
  • Reduction techniques MCQs
• Computational Complexity MCQs
  • Time complexity classes (P, NP, NP-complete, NP-hard) MCQs
  • Space complexity classes (PSPACE, L, NL) MCQs
  • Polynomial time reductions MCQs
• Advanced Topics in Automata Theory
  • Linear-bounded automata MCQs
  • Context-sensitive grammars and languages MCQs
  • Chomsky hierarchy MCQs
  • Introduction to quantum automata MCQs
• Applications of Automata Theory MCQs