finite state machine

(redirected from Deterministic automata)
Also found in: Encyclopedia.

finite state machine

n.
A model of a computational system, consisting of a set of states, a set of possible inputs, and a rule to map each state to another state, or to itself, for any of the possible inputs. The computational core of a Turing machine is a finite state machine. Also called finite state automaton.
References in periodicals archive ?
For instance, SageMath's package implements Moore's algorithm for minimization of deterministic automata, which has a polynomial worst case complexity [33, Sec.
First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant.
Thus, for this family, replacing the classical one-way deterministic automata even by two-way nondeterministic automata does not help to save a single state.
In Section 5, we show that the trade-off for the case of Las Vegas probabilistic versus one-way deterministic automata is different; by turning from language recognition to promise problems the tight quadratic gap changes to a tight exponential gap.
From regular expressions to deterministic automata.
It evoked noticeable interest among speciali= sts in graph theory, deterministic automata and symbolic dynamics, though r= emained unsolved - until Trahtman proposed his solution this past September.
These solutions include automata which are basically nondeterministic but contain a few transitions characteristic of deterministic automata.
In order to construct an automaton for the union language, she did not use the relatively simple algorithm for NFAs but decided to use the Cartesian product algorithm, though it was defined only for deterministic automata and results in a very complicated automaton.
Since soliton automata are proposed as switching devices, deterministic automata are in the center of investigations.
Full browser ?