Home › Quizzes › Automata Theory

Automata Theory

This quiz covers the fundamental concepts of Automata Theory, including finite automata, regular expressions, and context-free grammars.

14 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

Which of the following is NOT a type of finite automaton?

  1. Deterministic Finite Automaton (DFA)
  2. Non-Deterministic Finite Automaton (NFA)
  3. Pushdown Automaton (PDA)
  4. Linear Bounded Automaton (LBA)
Question 2 Multiple Choice (Single Answer)

What is the purpose of a regular expression?

  1. To describe a set of strings
  2. To parse a string according to a given grammar
  3. To generate a random string
  4. To compress a string
Question 3 Multiple Choice (Single Answer)

Which of the following is NOT a type of context-free grammar?

  1. Chomsky Normal Form (CNF)
  2. Greibach Normal Form (GNF)
  3. Regular Grammar
  4. Context-Sensitive Grammar
Question 4 Multiple Choice (Single Answer)

What is the Pumping Lemma for regular languages?

  1. For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is also in L for all i ≥ 0.
  2. For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is not in L for all i ≥ 0.
  3. For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is in L for all i ≤ 0.
  4. For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is not in L for all i ≤ 0.
Question 5 Multiple Choice (Single Answer)

What is the Myhill-Nerode Theorem?

  1. For any regular language L, there exists a unique minimal DFA that accepts L.
  2. For any regular language L, there exists a unique minimal NFA that accepts L.
  3. For any regular language L, there exists a unique minimal PDA that accepts L.
  4. For any regular language L, there exists a unique minimal LBA that accepts L.
Question 6 Multiple Choice (Single Answer)

Which of the following is NOT a closure property of regular languages?

  1. Union
  2. Intersection
  3. Concatenation
  4. Complement
Question 7 Multiple Choice (Single Answer)

What is the Chomsky Hierarchy?

  1. A hierarchy of formal grammars that classifies languages based on their generative power.
  2. A hierarchy of finite automata that classifies languages based on their acceptance power.
  3. A hierarchy of regular expressions that classifies languages based on their descriptive power.
  4. A hierarchy of context-free grammars that classifies languages based on their parsing power.
Question 8 Multiple Choice (Single Answer)

Which of the following is NOT a type of Turing machine?

  1. Deterministic Turing Machine (DTM)
  2. Non-Deterministic Turing Machine (NTM)
  3. Universal Turing Machine (UTM)
  4. Linear Bounded Automaton (LBA)
Question 9 Multiple Choice (Single Answer)

What is the Church-Turing Thesis?

  1. Any computation that can be carried out by a Turing machine can also be carried out by a human computer.
  2. Any computation that can be carried out by a human computer can also be carried out by a Turing machine.
  3. Any computation that can be carried out by a Turing machine can also be carried out by a quantum computer.
  4. Any computation that can be carried out by a quantum computer can also be carried out by a Turing machine.
Question 10 Multiple Choice (Single Answer)

Which of the following is NOT a decidable problem?

  1. The Halting Problem
  2. The Post Correspondence Problem
  3. The Traveling Salesman Problem
  4. The Graph Isomorphism Problem
Question 11 Multiple Choice (Single Answer)

What is the Rice's Theorem?

  1. Any non-trivial property of the set of all Turing machines is undecidable.
  2. Any non-trivial property of the set of all regular languages is undecidable.
  3. Any non-trivial property of the set of all context-free languages is undecidable.
  4. Any non-trivial property of the set of all recursively enumerable languages is undecidable.
Question 12 Multiple Choice (Single Answer)

Which of the following is NOT a type of language?

  1. Regular Language
  2. Context-Free Language
  3. Context-Sensitive Language
  4. Recursively Enumerable Language
Question 13 Multiple Choice (Single Answer)

What is the Greibach Normal Form (GNF) for context-free grammars?

  1. A context-free grammar in which every production is of the form A → aB or A → a, where A and B are non-terminals and a is a terminal.
  2. A context-free grammar in which every production is of the form A → BC or A → a, where A, B, and C are non-terminals and a is a terminal.
  3. A context-free grammar in which every production is of the form A → aBC or A → a, where A, B, and C are non-terminals and a is a terminal.
  4. A context-free grammar in which every production is of the form A → BC or A → a, where A and B are non-terminals and a is a terminal.
Question 14 Multiple Choice (Single Answer)

Which of the following is NOT a type of parsing?

  1. Top-Down Parsing
  2. Bottom-Up Parsing
  3. Left-to-Right Parsing
  4. Right-to-Left Parsing
← Back to Quizzes