Information Technology Reference
In-Depth Information
Fig. 6.3
A nondeterministic (top) automaton and a deterministic (bottom) automaton recog-
nizing
L(
ab
(
a
+
b
+
c
)
∗
(
a
+
c
))
states if
M
1
with the initial state of
M
2
, we get an automaton recognizing
L
1
L
2
.If
the two initial states of
M
1
and
M
2
are “fused” in a unique initial states connecting
the remaining parts of the two graphs, then we get an automaton recognizing the
language
L
1
+
·
L
2
. Finally, if a graph describes the transitions of an automaton
M
recognizing
L
, when in the graph of
M
, any transition edge entering in a final state,
is replicated by a new transition edge which connects that final state with the initial
of
M
, then a new automaton is obtained which recognizes the language correspond-
ing to
L
∗
. These three constructions define a general procedure for constructing an
automaton equivalent to a given regular expression.
The more complex part of the proof concerns the identification of the regular
language recognized by a given finite state automaton. We will show that it can
be obtained by applying the operation of sum, iteration, and Kleene star by start-
ing from finite languages. The proof we report is the original one of Kleene. It is
