Finite State Machine


Also found in: Dictionary, Acronyms, Wikipedia.

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 ?
These features include selective triple modular redundancy (TMR), fault-tolerant error correcting code (ECC) memory inference and the creation of finite state machine (FSM) utilizing Hamming-3 encoding for detection and correction of radiation-induced soft errors.
Since the IVR system is modelled as a Finite State Machine, the Flow Decider is used to keep track of the state of execution in the IVR system.
We can create concept of fuzzy group on a fuzzy finite state machine.
Controller 1 (C1) replicated the finite state machine implemented in a commercially available device: the i-limb prosthetic hand (Touch Bionics; Mansfield, Massachusetts) (Figure 1).
The second task is to process these data according to finite state machine to make a decision.
In order to provide increased branch prediction accuracy with low area and power overheads, in this paper we propose a novel adaptive learning machine-based shadow dynamic finite state machine (SDFSM).
4 Finite State Machine Availability, based evaluation model Reliability and for evaluating the Service functional metrics of Interruption any business logic by time are also checking whether checked.
To help accelerate the development of high-performance applications, the software also features new design examples showing how to utilize Spacetime technology with its many-ported memory blocks and how to build high-performance, small-footprint finite state machines (FSM) using ROM structures.
This paper continues the previous work by modifying the finite state machine model in order to provide additional support for implementing a safety mechanism.
Designers can now purchase either the dual or single language variant depending on their needs in finite state machine design and verification.
Advanced Lint capabilities include extensive finite state machine (FSM) checks and audit capabilities, dead code checks, parallel and full-case pragma verification, bus contention and floating bus detection.

Full browser ?