Finite State Machine

(redirected from Accepting state)
Also found in: Dictionary.
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].
Mentioned in ?
References in periodicals archive ?
Clearly, P(U) can be solved by a 1DFA D with only two states, counting the length of the input modulo 2, switching between an accepting state and a rejecting state.
Classical automata on promise problems
Therefore, A has an accepting alternating subtree rooted in [i.sub.x] at the end of the input if and only if [i.sub.x] is an accepting state. By definition of accepting states in A (the states of type [i.sub.0] are accepting but those of type ii are not), this holds if and only if x = 0, which in turn holds if and only if x = 0 = [b.sub.l'i], the ith bit of l.
Classical automata on promise problems
Last week, Hyundai increased its quarterly net profit by 13 per cent to $2 billion, but several European automakers felt the squeeze of the region's debt crisis, with Peugeot accepting state aid and even leader Volkswagen reporting lower profits.
Honda cuts full-year net profit forecast
Royce West of Dallas and Wendy Davis of Fort Worth, on how state accountability measures would apply to private schools accepting state funds, whether families could afford tuition costs above state vouchers and how effective the competition would be if public and private schools were not operating on a level playing field (private schools could choose which students to accept).
Senate Hearing Tackles Vouchers, School Choice
Figure 4 Bayesian Hypothesis Statements State A : [mu] = [[mu].sub.A] with Prior Probability = [P.sub.A] State B : [mu] = [[mu].sub.B] with Prior Probability = [P.sub.B] The cost of accepting state A when state B is true (cost (A|B)) is compared to the cost of accepting state B when state A is true (cost (B|A)).
Hypothesis testing: a look at two common approaches: depending upon the situation, either classical or Bayesian testing may be the better choice
Meanwhile, the outcome is awaited of a Finance Ministry investigation into what lf, the church has been doing with its financial ho support from the state (this latter episode caused critics to say that while some in the of church leadership objected to scrutiny by in the Dossier Commission, they did not mind accepting state money.)
The Bulgarian orthodox church: angels and demons? The State Security scandal is likely to prove damaging but not, ultimately, destructive
Joliet is planning to transfer foster children from Catholic Charities to different agencies while Springfield has decided to stop accepting state funds for foster care and continue the service on its own dime.
Catholic charities drops III. foster care lawsuit
After all our trading partners in Europe have no difficulty in accepting state ownership that competes in the market place.
We must create a just, fair society; Views of the North
Basically, they provided for formation of a not-for-profit entity in this case, Strandberg and Rodvik said, more of a custom-designed corporation with broad responsibility for keeping the lights on and dealing in billions of dollars in utility projects, notably including borrowing money and accepting State appropriations.
Railbelt electricity: obstacles to one-utility approach
(24) For example, Article 121(5) may be read to exempt nationals of non-accepting States Parties from prosecution for the crime of aggression, even if committed on the territory of an accepting State Party.
Bringing the crime of aggression within the active jurisdiction of the ICC
A waiting period, however, would ease doubts about lawmakers' motivations in accepting state jobs.
Slow the revolving door
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.
From the U.S. Department of Education

Encyclopedia browser ?
Full browser ?