dict.org

The DICT Development Group


Search for:
Search type:
Database:

Database copyright information
Server information


1 definition found
 for finite state machine
From The Free On-line Dictionary of Computing (30 December 2018) :

  Finite State Machine
  acceptor
  Finite Automata
  Finite Automaton
  Finite State Automata
  Finite State Automaton
  NFA
  
      (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 [proper name?], 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].
  
     (2001-09-22)
  

Contact=webmaster@dict.org Specification=RFC 2229