Finite State Machine

(redirected from Start state)
Also found in: Dictionary.

Finite State Machine

(mathematics, algorithm, theory)
(FSM or "Finite State Automaton", "transducer") An abstract machine consisting of a set of states (including the initial state), a set of input events, a set of output events, and a state transition function. The function takes the current state and an input event and returns the new set of output events and the next state. Some states may be designated as "terminal states". The state machine can also be viewed as a function which maps an ordered sequence of input events into a corresponding sequence of (sets of) output events.

A deterministic FSM (DFA) is one where the next state is uniquely determinied by a single input event. The next state of a nondeterministic FSM (NFA) depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in.

It is possible to automatically translate any nondeterministic FSM into a deterministic one which will produce the same output given the same input. Each state in the DFA represents the set of states the NFA might be in at a given time.

In a probabilistic FSM there is a predetermined probability of each next state given the current state and input (compare Markov chain).

The terms "acceptor" and "transducer" are used particularly in language theory where automata are often considered as abstract machines capable of recognising a language (certain sequences of input events). An acceptor has a single Boolean output and accepts or rejects the input sequence by outputting true or false respectively, whereas a transducer translates the input into a sequence of output events.

FSMs are used in computability theory and in some practical applications such as regular expressions and digital logic design.

See also state transition diagram, Turing Machine.

[J.H. Conway, "regular algebra and finite machines", 1971, Eds Chapman & Hall].

[S.C. Kleene, "Representation of events in nerve nets and finite automata", 1956, Automata Studies. Princeton].

[Hopcroft & Ullman, 1979, "Introduction to automata theory, languages and computations", Addison-Wesley].

[M. Crochemore "tranducters and repetitions", Theoritical. Comp. Sc. 46, 1986].
References in periodicals archive ?
6), the Off State voltages, the On State voltages and currents, and the Start State voltages and currents are given in periods of 4 seconds.
(ii) The start state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.
The model was first constructed to produce all the results for Transition Probability Matrix, Initial Probability Matrix and Observable/Emission Symbols/Words contained in the data sets, with the start state having a transition being represented by a unique path with one state per tag.
From the start state [q.sub.0] we make a [lambda] move to state [q.sub.5].
The agent begins in a start state, or set of start states, and receives a positive reward upon reaching a goal state based on how many actions it has executed.
A one-way (Kondacs-Watrous) quantum finite automaton with restart ([1QFA.sup.[??]]) is a where the reset moves can target only the original start state, and,
Suppose if A has only one start state [q.sub.0] then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
* $5 billion for Temporary Assistance for Needy Familles (TANF) state block grant's emergency fund; $2 billion for the Child Care Development state block grant; $1 billion for the Head Start state block grant; and $1 billion for the Community Services state block grant.
On the domestic front, Yogen Fruz announced that YF Systems of Texas, LLC, will be opening up a series of franchise locations across the Lone Start State. YF Systems plans to open 30 locations over the next ten years and will call on its past franchising experience to contribute to the development and growth of the Yogen Fruz brand in Texas.
The programs were intended to jump start state and local initiatives to address their water/wastewater environmental problems quickly.
An FSM consists of a set of possible states, a start state, an input alphabet, a transition function and an output alphabet.
In order to match the goal configuration, participants operated on the start state in the lower half of the screen by moving the balls with a computer mouse.