Coursify

Push-Down Automaton and Grammar Classes (MCQ Practice)

Push-Down Automaton and Grammar Classes (MCQ Practice)

Verified Sources
Nov 3, 2026

A push-down automaton (PDA) is a type of automaton equipped with a stack, and it recognizes exactly the class of keyword context-free languages—equivalently, the languages generated by keyword context-free grammars .
Therefore, among the options, the correct grammar type recognized by a PDA is (ii) Context-free.

Footnotes

  1. (Wikipedia) Pushdown automaton — https://en.wikipedia.org/wiki/Pushdown_automaton - Explains that PDAs recognize exactly the context-free languages (equivalent to context-free grammars). ↩

Context-Free Languages & Pushdown Automata (PDA) Overview

Key idea

A PDA can use its stack to keep track of nested structures (e.g., matching parentheses), which is the hallmark of context-free grammars.

  • keyword Pushdown automaton (PDA)
  • keyword Context-free grammar (CFG)
  • keyword Context-free language (CFL)
  • keyword Regular language

From Automata to Grammar Types

Finite automaton

Step 1

Recognizes keyword regular languages."

Pushdown automaton

Step 2

Adds a stack; recognizes keyword context-free languages."

Linear bounded automaton

Step 3

Characterizes keyword context-sensitive languages."

Exam shortcut

Finite automaton → Regular; Pushdown automaton → Context-free; Linear bounded automaton → Context-sensitive.

Common mistake

Many students think “more power than regular” means “context-sensitive or unrestricted.” PDA is still limited to context-free (not context-sensitive).

How to select the correct option (PDA → Grammar Type)

  1. 1
    Step 1

    The question asks about a push-down automaton (PDA), which has a stack.

  2. 2
    Step 2

    PDA-recognizable languages are exactly the context-free languages (equivalently, CFG-generated languages).

    Footnotes

    1. (Wikipedia) Pushdown automaton — https://en.wikipedia.org/wiki/Pushdown_automaton - Explains that PDAs recognize exactly the context-free languages (equivalent to context-free grammars). ↩

  3. 3
    Step 3

    Context-free is option (ii).

  4. 4
    Step 4

    Stack supports matching/nesting (like ()()), which is context-free behavior.

    Footnotes

    1. (Wikipedia) Pushdown automaton — https://en.wikipedia.org/wiki/Pushdown_automaton - Explains that PDAs recognize exactly the context-free languages (equivalent to context-free grammars). ↩

Automaton Power vs Grammar Type (Conceptual)

Where PDA fits in the Chomsky hierarchy

Quick FAQ

Knowledge Check

Question 1 of 3
Q1Single choice

Which grammar type is recognized by a push-down automaton?

Explore Related Topics

1

Handle Pruning and the Correct Parsing Method (MCQ)

2

Correct Answer: Eliminating Immediate Left Recursion \(A \rightarrow A\alpha / \beta\)

3

Correctness of CFL Closure / Automaton Statements (CFLs, DPDA, Complement)

Browse all research articles