finite state machine

(redirected from Finite state 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 ?
We assume the reader is familiar with the basic standard models of finite state automata (see e.g.
Regular grammars: the languages defined by these grammars are accepted by finite state automata. There are two kinds of regular grammars:
Finite State Automata. A DFA is a 5-tuple (Q, [SIGMA], [delta], i, F), where Q is a set of states, [SIGMA] is an alphabet, i is the initial state, F [subset or equal to] Q is a set of final states, and [delta] is a transition function mapping Q x [SIGMA] to Q.
The language containment of deterministic finite state automata can be checked in polynomial time [19].
Other topics include regular path queries of graph-structured data, finite state automata in compiler, Petri nets, and model checking.
The class of languages accepted by PDA is the class of context-free languages which strictly includes the class of regular languages (accepted by finite state automata) and is strictly contained in the class of recursive enumerable languages (accepted by Turing machines).
As in the classical automata theory, there are deterministic and non-deterministic finite state automata deals with probabilistic processes [5].
(2000, 2001) han enfocado el tema de la inferencia de NFAs desde la parte teorica, al centrarse en un subconjunto de los NFAs, llamado RFSA (Residual Finite State Automata).
Finite State Automata utilities An open-source free toolkit.
McGinnity, "Automatically composing and parameterizing skills by evolving Finite State Automata," Robotics and Autonomous Systems, vol.
On the power of quantum finite state automata. In FOCS'97: Proceedings ofthe 38th Annual Symposium on Foundations ofComputer Science, pages 66-75, 1997.
Full browser ?