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 ?
The State Department of Education, First Things First and Arizona Head Start State Collaboration Office also played key roles in committing statewide efforts to "put a stake in the ground" around third-grade reading.
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.
is a where the reset moves can target only the original start state, and,
Within a range of three moves away from the start state or a goal move on the optimal solution path, suboptimal alternatives compete with the optimal solution and allow to solve a problem in one to two additional subgoal moves.
In the Antelope Valley, there are three preschools operated by school districts - two in the Lancaster School District and one Head Start state preschool in the Palmdale School District.
Santanee Phasuk and Philip Start state that, from close study of the maps' internal historical evidence, orthography and artistic style, they "may thus well be the only extant maps from the early reigns of the Chakri dynasty" (Kings Rama I-III inclusive; from the late 18th to mid-19th centuries).
In other situations we have a start state ("Before, Juan had 2 pesetas"), a variation ("then he earned 3 pesetas") and an end state ("Juan has now 5 pesetas").
We choose the minimum temporal distance between state i and the start state ([s.
Florida's Department of Education and Region IV Head Start, in collaboration with the Florida Head Start State Collaboration Office, set up meetings for vendors and program administrators to discuss early childhood assessment and evaluate the different online assessment options available for early childhood programs.
A (computation) path is therefore a sequence of transitions such that the end state of each transition is the start state of the next transition.
This experiment models the system beginning at a start state, and going for t' + [n.
Persistent lobbying by US-based United Parcel Service plus a five-year court case over the European Commission's reluctance to start state aid proceedings against German postal operator Deutsche Post have paid off for Europe's private postal operators.