Finite State Machine

(redirected from Accepting state)
Also found in: Dictionary, Wikipedia.
Related to Accepting 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 ?
This summer, the Department of Education begins accepting state applications for the federal government's largest one-time investment in K-12 public school reform.
Ruane said that when the ruling was made 10 days ago, the men were "faced with the decision of accepting state security or making their own arrangements".
His first step was accepting state and regional government relations responsibilities for the Appraisal Institute, followed by becoming nationally active by working with the Region X state lobbyist, the national Government Relations Committee and the Washington, D.
5 standard, it ordered the agency to do more work on the ozone standard and 2) as the implementation plan shows, EPA will have some leeway in designating non-attainment areas and accepting state plans.
This kind of accepting state of mind for "favorable" beliefs is not going to help our argument that humanism depends on unfettered inquiry and reason.
A few have chosen outright defiance, some have engaged in silent protest while others have acquiesced in government do minance of religion by tacitly accepting state control.
Such protections make it more likely that evangelical Christian groups already fighting poverty will be able to expand their activities by accepting state money.
It would require all businesses accepting state EBT cards to post fraud hotline phone numbers to report suspected misuse of benefits.
In a state where schools have cut back on faculty and electives, school districts are restricted to emergency maintenance only and "closure days" are instituted to save money, how can anyone be excited about accepting state tax money back?
The 23 articles approved May 3 involved reauthorization of existing revolving funds, accepting state funds for highway projects, and amending a number of personnel and zoning bylaws, none of which involved expenditure of town-generated money.
Accepting state parks grant for Mingus Park ballfield lightpole replacement and bleacher project; telecommunications business license ordinance; report on Newmark Improvement Project; revenue issues for 2002-03 budget; executive (nonpublic) session to discuss labor negotiations.