from
The Free On-line Dictionary of Computing (8 July 2008)
Finite State Machine
acceptor
Finite Automata
Finite Automaton
Finite State Automata
Finite State Automaton
NFA
<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 [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)
from
Bouvier's Law Dictionary, Revised 6th Ed (1856)
ACCEPTOR, contracts. The person who agrees to pay a bill of exchange drawn
upon him. There cannot be two separate acceptors of a bill of exchange, e.
g. an acceptance by the drawee, and another for the honor of some party to
the bill. Jackson v. Hudson, 2 Campb. N. P. C. 447.
2. The acceptor of a bill is the principal debtor, and the drawer the
surety. He is bound, though he accepted without consideration, and for the
sole accommodation of the drawer. By his acceptance he admits the drawer's
handwriting, for, before acceptance it was incumbent upon him to inquire
into the genuineness of the drawer's handwriting. 3 Burr. 1354; 1 Bla. Rep.
390, S. C.; 4 Dall. 234; 1 Binn. 27, S. C. When once made, the obligation of
the acceptor is irrevocable. As to what amounts to an acceptance, see ante,
Acceptance; Chitty on Bills, 242, et. seq.; 3 Kent, Com. 55, 6; Pothier,
Traite du Contrat de Change, premiere part. n. 44.
3. The liability of the acceptor cannot in general be released or
discharged, otherwise than by payment, or by express release or waiver, or
by the act of limitations. Dougl. R. 247. What amounts to a waiver and
discharge of the acceptor's liability, must depend on the circumstances of
each particular case. Dougl. 236, 248; Bayl. on Bills, 90; Chitty on Bills,
249.