OnlineWoerterBuecher.de - Lexikon, Free On-line Dictionary of Computing



	OnlineWoerterBuecher.de

Navigation

Start

Deutsch-Englisch

Deutsch-Spanisch

Enzyklopädie

Internes

Impressum

Kontakt

Lexikon

Finite State Machine

(FSM or "Finite State Automaton", "transducer") An href="module.php?name=Lexikon&file=search&eid=1&query=abstract machine">abstract machine consisting of a set of href="module.php?name=Lexikon&file=search&eid=1&query=states">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 href="module.php?name=Lexikon&file=search&eid=1&query=deterministic">deterministic FSM (DFA) is one where the next state is uniquely determinied by a single input event. The next state of a href="module.php?name=Lexikon&file=search&eid=1&query=nondeterministic">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 [proper name?], there is a predetermined href="module.php?name=Lexikon&file=search&eid=1&query=probability">probability of each next state given the current state and input (compare href="module.php?name=Lexikon&file=search&eid=1&query=Markov chain">Markov chain). The terms "acceptor" and "transducer" are used particularly in language theory where automata are often considered as href="module.php?name=Lexikon&file=search&eid=1&query=abstract machines">abstract machines capable of recognising a language (certain sequences of input events). An acceptor has a single href="module.php?name=Lexikon&file=search&eid=1&query=Boolean">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 href="module.php?name=Lexikon&file=search&eid=1&query=computability theory">computability theory and in some practical applications such as href="module.php?name=Lexikon&file=search&eid=1&query=regular expressions">regular expressions and digital logic design. See also href="module.php?name=Lexikon&file=search&eid=1&query=state transition diagram">state transition diagram, href="module.php?name=Lexikon&file=search&eid=1&query=Turing Machine">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]. (2001-09-22)

[ Go Back ]

Free On-line Dictionary of Computing

	All logos and trademarks in this site are property of their respective owner. Page Generation in 0.1015 Seconds, with 16 Database-Queries