Finite State Machine

(redirected from Accept state)
Also found in: Dictionary.
Related to Accept state: State transition function

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 (

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 ?
On the other hand, the fact that thus far the leaders of the Albanian parties did not accept state position, according to experts, is avoiding assuming responsibility.
"March 8"refuses to accept state as reference "Resistance" rejects "Bbda Declaration" from Bbda AL-AKHBAR: Decisive Friday: Ministerial statement or resignation THE DAILY STAR: Eleventh-hour bid to salvage Cabinet The Cabinet will meet again Friday in an eleventh-hour attempt to avert a government crisis over its policy statement in the shadow of a threat by Prime Minister Tammam Salam to resign.
However, after striking a deal to accept state financing, Pitney said it would stay in Stamford and add 200 jobs across its Fairfield county operations.
Sunas tagged her as a conduit and gatekeeper of a web of fake of NGOs sanctioned to accept state money for livelihood projects for the last two years.
In areas where the law prohibits HHS from completely delegating responsibility to a state, HHS said it will work with states to agree upon processes that help HHS accept state recommendations without the need for duplicative reviews from HHS.
Critics also are concerned about how state accountability measures would apply to private schools that accept state funds, and whether families could afford transportation and tuition costs in addition to state vouchers.
Figure 6 Bayesian Decision Rule O" R > 1, accept state A O" R < 1, accept state B Classical hypothesis testing can be used in situations where plausible inferences about a population can be made.
Hope said some parents drive their children farther, to the South or West sides, for child care providers who accept state and city vouchers.
Taken together, the legislation's provisions would create a serious disincentive for centers to accept state child care subsidies.
* Upon reaching any accept state of [A.sub.i,j] (0 [less than or equal to] i, j < k), M moves the head back to the left end-marker and then switches to the start state of [A.sub.i+1j];
Lopez said he had not seen a list of what kinds of insurance was approved and from which countries, but said he had been told Cuba will accept state or private insurance from any country except the United States.
Although differing in size and political environment, both had splits between the state-recognized and state-tolerated Baptists and those who refused to accept state authority over them.