Finite State Machine

(mathematics, algorithm, theory)(FSM or "Finite StateAutomaton", "transducer") An abstract machine consisting ofa set of states (including the initial state), a set ofinput events, a set of output events, and a state transitionfunction. The function takes the current state and an inputevent and returns the new set of output events and the nextstate. Some states may be designated as "terminal states".The state machine can also be viewed as a function which mapsan ordered sequence of input events into a correspondingsequence of (sets of) output events.

A deterministic FSM (DFA) is one where the next state isuniquely determinied by a single input event. The next stateof a nondeterministic FSM (NFA) depends not only on thecurrent input event, but also on an arbitrary number ofsubsequent input events. Until these subsequent events occurit is not possible to determine which state the machine is in.

It is possible to automatically translate any nondeterministicFSM into a deterministic one which will produce the sameoutput given the same input. Each state in the DFA representsthe set of states the NFA might be in at a given time.

In a probabilistic FSM there is apredetermined probability of each next state given thecurrent state and input (compare Markov chain).

The terms "acceptor" and "transducer" are used particularly inlanguage theory where automata are often considered asabstract machines capable of recognising a language (certainsequences of input events). An acceptor has a singleBoolean output and accepts or rejects the input sequence byoutputting true or false respectively, whereas a transducertranslates the input into a sequence of output events.

FSMs are used in computability theory and in some practicalapplications such as regular expressions and digital logicdesign.

See also state transition diagram, Turing Machine.

[J.H. Conway, "regular algebra and finite machines", 1971, EdsChapman & Hall].

[S.C. Kleene, "Representation of events in nerve nets andfinite 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].

单词	finite state machine
释义	finite state machine finite state machine n. A model of a computational system, consisting of a set of states, a set of possible inputs, and a rule to map each state to another state, or to itself, for any of the possible inputs. The computational core of a Turing machine is a finite state machine. Also called finite state automaton. Finite State Machine Finite State Machine (mathematics, algorithm, theory)(FSM or "Finite StateAutomaton", "transducer") An abstract machine consisting ofa set of states (including the initial state), a set ofinput events, a set of output events, and a state transitionfunction. The function takes the current state and an inputevent and returns the new set of output events and the nextstate. Some states may be designated as "terminal states".The state machine can also be viewed as a function which mapsan ordered sequence of input events into a correspondingsequence of (sets of) output events. A deterministic FSM (DFA) is one where the next state isuniquely determinied by a single input event. The next stateof a nondeterministic FSM (NFA) depends not only on thecurrent input event, but also on an arbitrary number ofsubsequent input events. Until these subsequent events occurit is not possible to determine which state the machine is in. It is possible to automatically translate any nondeterministicFSM into a deterministic one which will produce the sameoutput given the same input. Each state in the DFA representsthe set of states the NFA might be in at a given time. In a probabilistic FSM there is apredetermined probability of each next state given thecurrent state and input (compare Markov chain). The terms "acceptor" and "transducer" are used particularly inlanguage theory where automata are often considered asabstract machines capable of recognising a language (certainsequences of input events). An acceptor has a singleBoolean output and accepts or rejects the input sequence byoutputting true or false respectively, whereas a transducertranslates the input into a sequence of output events. FSMs are used in computability theory and in some practicalapplications such as regular expressions and digital logicdesign. See also state transition diagram, Turing Machine. [J.H. Conway, "regular algebra and finite machines", 1971, EdsChapman & Hall]. [S.C. Kleene, "Representation of events in nerve nets andfinite 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]. See FSM See FDDI Switching Module
随便看	dutch treats dutch type library dutch uncle dutch uncles dutch uncle, talk (to one) like a dutch united nations student association dutch university institute for art history dutch validation council dutch valley church of god dutch version of the arthritis impact measurement scales 2 dutch voluntary euthanasia society dutch warmblood dutch warmblood association dutch war of 1672–78 dutch wars dutch wars of the 17th century dutch web promotion dutch west india dutch west india company dutch west indies dutch west indies company dutch west new guinea dutch wife dutch wifes dutchwoman

finite state machine

finite state machine

Finite State Machine

Finite State Machine