Pushdown automaton
Overview
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
, a pushdown automaton (PDA) is a finite automaton
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
that can make use of a stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
containing data.
Pushdown automata differ from finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
s in two ways:
- They can use the top of the stack to decide which transition to take.
- They can manipulate the stack as part of performing a transition.
Pushdown automata choose a transition by indexing a table by input signal, current state, and the symbol at the top of the stack.
