Pushdown automaton

A pushdown automaton is a finite-state machine equipped with a stack, whose stack operations let it recognize context-free languages.

Stack alphabet: A finite set of symbols that a pushdown automaton can store on its stack. These symbols are the automaton’s writable memory.
Finite-state machine: A computational model with finitely many states and transitions, but no unbounded memory. The automaton’s control component is a finite-state machine.
Dyck language: A language of balanced strings of parentheses or other matched delimiters. A stack tracks unmatched opening delimiters while recognizing these strings.
Finite automaton: A machine with finitely many states that recognizes regular languages without auxiliary memory. Its memory is bounded, unlike the potentially unbounded stack here.
Transition function: A rule mapping a machine’s current state and input to permitted next states and actions. It specifies state changes, input consumption, and stack operations.
Stack (abstract data type): A data structure that adds and removes elements according to last-in, first-out order. The automaton’s memory follows this last-in, first-out discipline.
Compiler: A program that translates source code into another representation, often machine code. Compiler syntax analysis commonly uses grammars with pushdown-automaton equivalents.
Turing machine: A computational model with a read-write tape that can move in both directions and support general computation. Its tape is more flexible than a pushdown automaton’s restricted stack.
Nondeterministic finite automaton: A finite-state machine that may follow multiple transitions for the same state and input. Without a stack, it cannot recognize every language this automaton can.
Context-free grammar: A formal grammar whose production rules replace a single nonterminal with a string of terminals and nonterminals. Its derivations describe the same languages recognized by nondeterministic pushdown automata.

Linked from 12 pages