Information Technology Reference
In-Depth Information
For the sake of brevity, usually we will avoid to provide all the transition rules
of a finite automaton. In fact, we adopt the convention that when a transition
is not explicitly given, it is assumed that the state specified by the missing
transition is a special non-final state, say it a
failure
state, which does not
belong the the final states, where the automaton remains for any other symbol
read in that state.
-transition, that is, the automaton can change
its state without reading any symbol. However, it can be shown that any automaton
with
In some cases it is useful to use
λ
λ
-transition has an equivalent automaton without
λ
-transitions.
}
∗
,
Let us consider the pattern
abxy
where
x
∈{
a
,
b
,
c
y
∈{
a
,
c
}
. The correspond-
ing regular expression is
)
∗
(
ab
(
a
+
b
+
c
a
+
c
)
)
∗
(
Figure 6.4 gives two automata recognizing the language
L(
ab
(
a
+
b
+
c
a
+
c
))
.
The automaton on the top is nondeterministic because reading the symbols
a
c
in
the top rightmost state different edges can be followed, by reaching different states.
On the bottom, an equivalent deterministic automaton is given. Usually, the nonder-
ministic automaton equivalent to a deterministic one has a simpler structure, but its
functioning is more complex (all the possible behaviors have to be considered for
recognizing a given string).
A result due to Kleene is expressed by the following proposition which we report
without proof.
,
Proposition 6.4.
Any language which is recognized by a nondeterministic finite
state automaton is also recognized by a suitable deterministic finite state automaton.
Finite state automata were inspired by studies in modeling of neurological activity.
The original paper of S. C. Kleene, in 1956, where these automata were introduced,
was entitled
Representation of events in nerve nets and finite automata
,which
was based of the fundamental paper of McCulloch and Pitts of 1943 (A logical
calculus of the ideas immanent in nervous activity).
Another result, proved by Kleene in the paper mentioned above, shows the equiv-
alence between FSA (Finite State Automata) and REG. In fact the following propo-
sition holds.
Proposition 6.5.
REG
FSA, that is, the class of languages generated by finite
languages by applying, a finite number of times, the operations of concatenation,
sum, and Kleene star, coincides with the class of languages recognized by finite
state automata.
≡
Proof.
Given a regular language
L
, a (nondeterministic) finite automaton recogniz-
ing it can be easily constructed. In fact, if a regular language
L
1
is recognized by
M
1
and a regular language
L
2
is recognized by
M
2
, then putting together the graphs
representing the transition rules of the automata
M
1
and
M
2
, and connecting the final
