Information Technology Reference
In-Depth Information
M
Q
Fig. 6.1
A finite state automaton at beginning of its functioning
read,
M
“accepts”
, if the state assumed by
M
belongs to the set of its
final
states.
Otherwise,
M
does not accept
α
the
language recognized
by
M
, that is, the set of strings which are accepted by the automaton
M
.
Figure 6.2 describes, by means of a graph, an automaton which recognizes the
bipartite language
α
. We denote by
L(
M
)
a
n
b
m
. Initial and final states are indicated by entering and
exiting arrows respectively that are not linked with other states.
L(
)
q
0
a
b
q
2
a
a
q
1
b
b
Fig. 6.2
A finite state automaton recognizing the bipartite language
The formal definition of finite state automaton follows.
Definition 6.2.
A (deterministic) finite state automaton
M
is given by the following
structure:
M
=(
A
,
Q
,
τ
,
F
,
q
0
)
