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].
References in periodicals archive ?
While the law does not allow HHS to completely delegate QHP certification to states with an FFE, HHS said it will work with states to agree upon processes that maximize the probability that HHS will accept state recommendations without the need for duplicative reviews from HHS.
Taken together, the legislation's provisions would create a serious disincentive for centers to accept state child care subsidies.
If the input is not a palindrome, the two amplitudes do not cancel each other completely, and the nonzero difference is transferred to an accept state.
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.
The Commission will not accept state aid conditional upon implementation of a specific business plan, negotiated with certain member states, that defines the geographical distribution of restructuring measures without giving the beneficiary companies the possibility to revise their plans if necessary," he explained.
The bank's chief executive officer, John Varley, is of the opinion that Barclays Plc can emerge from the credit crisis as a full-service, global bank if it doesn't accept state aid and the restrictions that come with it.
It was sparked by public outrage on huge bonuses paid to bankers such as former UBS chairman Marcel Ospel, even though the bank lost billions in the sub-prime crisis and was forced to accept state help worth almost $60 billion.
But what civil servants don't appreciate is that many pensioners find the paperwork to get their extra cash too complicated and that many come from a generation which is too proud to accept state hand-outs.
accept state indoctrination that the homosexual lifestyle is normal and to be honoured).
Several federal agencies, including the SEC, the GAO, and the IRS, accept state licensure but regulate to sets of regulations and rules that vary in their explicitness.