re 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].

Last updated: 2001-09-22

Nearby terms:

apsdingre is addison-Wesley].ers and repetitions",ount of

Try this search on Wikipedia, OneLook, Google