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].
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

state machine

Also called a "finite state machine," it is a computing device designed with the operational states required to solve a specific problem. The circuits are minimized, specialized and optimized for the application. For example, chips in audio, video and imaging controllers are often designed as state machines, because they can provide faster performance at lower cost than a general-purpose CPU. Automatic ticket dispensing machines are another example. There are countless special-purpose devices built as state machines. See SDL and cellular automaton.
Copyright © 1981-2019 by The Computer Language Company Inc. All Rights reserved. THIS DEFINITION IS FOR PERSONAL USE ONLY. All other reproduction is strictly prohibited without permission from the publisher.
References in periodicals archive ?
The first step of the verification process consists of building a set of finite state machines based on the specification of the subsystem.
Choudhury, "Low power and high testable Finite State Machine synthesis," in Proceedings of the International Conference and Workshop on Computing and Communication, IEMCON2015,pp.
described an efficient parallel algorithm that uses manycore GPUs for automatically deriving UIOs from Finite State Machines [34].
For the purpose of obtaining the human exercise health, we propose a novel exercise health simulation approach, which comprises an integrated thermophysiological model and a fuzzy finite state machine. Some common physiological indicators like core temperature, dehydration amount, and heart rate used in exercise health prognosis can be well simulated by our thermophysiological model.
Having the finite state machine module readily available in a publicly available and continuously maintained system also leads to more transparency in the computational parts of publications.
Defining a single complexity measure for the application of model checking to finite state machines is in general not possible.
(1) According to the theory of finite state machine and the mission requirement of UAVs formation, we can determine five models of UAV formation as follows: free formation flight [S.sub.1]; forming the initial formation [S.sub.2]; keeping the formation S3; formation reconfiguration [S.sub.4]; formation avoidance control [S.sub.5].
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.
Modular finite state machines (MFSMs) are a low-level logic control language built on the concept of FSM [8].
Malik et al in [3] introduced the notion of subsystems of a fuzzy finite state machine in order to consider state membership as fuzzy .
Previous works have compared pattern recognition MECs [17] and finite state machine MECs [11] but not the more recently proposed PC schemes.
Apple's patent describes the use of a finite state machine or FSM and a server.

Full browser ?