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.
Now we consider a start state s ("this morning J had 2 pta"), time goes by and we have the end state e ("J has now 5 pta"), and there is a variation v = e - s ("J has earned 3 pta").
i] is greatest for those states in between the goal and start states and least for those states near the goal or start states.
Also includes Head Start State Preschool, which serves approximately 1,350 children in the Antelope Valley
The department also houses the Head Start State Collaboration Office, distributes federal funding to enhance the quality and availability of child care, and works collaboratively with Georgia child care resource and referral agencies and organizations throughout the state to enhance early care and education.
However, these probate orders do not exist in many cases and it can be costly and time consuming to start state or tribal probate proceedings.
That is where the deficiency rests, with the board,'' said Carolyn Mangrum, interim director for the Head Start State Preschool Program at the Los Angeles County Office of Education, who has attended every meeting since November.
The HYBRID CNG engine in the CN 380 seamlessly allows the driver to utilize the regular gasoline engine when the CNG fuel is depleted, and also automatically uses the gasoline as fuel to run the engine when it is in a cold start state and the engine is warming up.
PALMDALE - Palmdale School District's Head Start state preschool program will hold a ``Kindergarten Transition'' meeting for parents from 7:30 a.
We are hopeful that this initiative will lead to local dentist-Head Start partnerships that will improve access to care for our children," said Gina Ruther, Head Start State Collaboration Director for the Illinois Department of Human Services.