Nested stack automaton
Encyclopedia
In automata theory
, a nested stack automaton is a finite automaton
that can make use of a stack
containing data which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an indexed language
.
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 nested stack automaton 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 which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an indexed language
Indexed language
Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automatons....
.