Which standard automaton model is equivalent in expressive power to a…

CONCEPT: A grammar class and an automaton class are equivalent when they describe exactly the same family of languages. Context-free grammars generate context-free languages, and nondeterministic pushdown automata recognize exactly this family by using a stack.

APPLICATION: A pushdown automaton uses its stack to remember nested or paired structure while reading the input. This memory is the standard automata-theoretic counterpart of derivations in a context-free grammar.

CONTRAST

• A finite-state automaton has no unbounded auxiliary memory and characterizes only regular languages.

• A two-way linear bounded automaton uses linearly bounded read-write tape and characterizes the broader context-sensitive family.

• The combined statement names two models with different expressive powers, so they are not both equivalent to context-free grammars.

CROSS-CHECK: The language consisting of n copies of a followed by n copies of b is context-free: a pushdown automaton can push one marker per a and pop one per b. A finite-state automaton cannot perform this unbounded matching, while a linear bounded automaton has more power than is required.

RESULT: The equivalent standard model is a pushdown automaton.