Finite-State Automaton (FSA; finite-state machine) Definition/Meaning:
A simple kind of automaton.
The input string is read once from left to right, looking at each symbol in
turn, At any time the FSA has some internal state, which changes after each
input symbol is read. The new state depends firstly on the symbol just read and
secondly on the current state. An FSA is therefore determined by a function ƒ
from I x Q to Q, where I is the set of possible input symbols, Q is the set of
states, and I x Q is the Cartesian product of I and Q. Q must be finite, hence
the name FSA.
The function ƒ is called a state transition function. It is
commonly represented either by a table or by a directed graph, known
respectively as a state transition table and a state transition diagram. The
figure shows two equivalent representations in which
I = (a,b,c),
Q = (1,2,3,4)
In this example,
ƒ(a,1) = 2
ƒ(c,4) = 4, etc.
ƒ extends to strings in the obvious manner:
in the example,
ƒ(b,c,2) = 4,
ƒ(aaa,3) = 1, etc.
Let Q be divided into accepting stales and rejecting states, and let
q0 be some
member of Q (referred to as the start state). The language recognized by the FSA
is the set of all w such that
ƒ(w,q0)
is an accepting state, i.e. the set of all strings that take the start state to
an accepting state. For example, in the FSA shown in the figure let q0 be 1 and
let 4 be the only accepting state; the language recognized is then the set of
all strings over {a,b,c} that somewhere contain abc as a substring.
A generalization is to allow more than one state to which the FSA can move, for
a given input symbol and current state. This gives a nondeterministic FSA. The
input string is then accepted if there is some sequence of choices of moves
leading to an accepting state. Such a machine can always be converted to a
deterministic one recognizing the same language.
See also sequential machine,
minimal machine.
|
