Information Technology Reference
In-Depth Information
Start
Start
Start
a
q
q
S
S
S
(a)
(b)
(c)
Figure 4.6
Finite-state machines recognizing the regular expressions
,
∅
,and
a
, respectively.
In b) an output state is shown even though it cannot be reached.
INDUCTION:
Assume that the hypothesis holds for all regular expressions
r
with at most
k
operators. We show that it holds for
k
+
1 operators. Since
k
is arbitrary, it holds for all
k
.
The outermost operator (the
k
+
1st) is either concatenation, union, or Kleene closure. We
argue each case separately.
CASE 1:
Let
r
=(
r
1
·
r
2
)
.
M
1
and
M
2
are the NFSMs that accept
r
1
and
r
2
, respectively.
By the inductive hypothesis, such machines exist. Without loss of generality, assume that the
states of these machines are distinct and let them have initial states
s
1
and
s
2
, respectively.
As suggested in Fig.
4.7
, create a machine
M
that accepts
r
as follows: for each input letter
σ
, final state
f
of
M
1
,andstate
q
of
M
2
reached by an edge from
s
2
labeled
σ
,addanedge
with the same label
σ
from
f
to
q
.If
s
2
is not a final state of
M
2
, remove the final state
designations from states of
M
1
.
It follows that every string accepted by
M
either terminates on a final state of
M
1
(when
M
2
accepts the empty string) or exits a final state of
M
1
(never to return to a state of
M
1
),
enters a state of
M
2
reachable on one input letter from the initial state of
M
2
, and terminates
on a final state of
M
2
.Thus,
M
accepts exactly the strings described by
r
.
CASE 2:
Let
r
=(
r
1
+
r
2
)
.Let
M
1
and
M
2
be NFSMs with distinct sets of states and let
initial states
s
1
and
s
2
accept
r
1
and
r
2
, respectively. By the inductive hypothesis,
M
1
and
M
2
exist. As suggested in Fig.
4.8
, create a machine
M
that accepts
r
as follows: a) add a
new initial state
s
0
; b) for each input letter
σ
and state
q
of
M
1
or
M
2
reached by an edge
y
x
x
f
1
q
1
y
y
z
f
3
s
1
M
1
M
2
s
2
f
2
q
2
x
z
z
Figure 4.7
Amachine
M
recognizing
r
1
· r
2
.
M
1
and
M
2
are the NFSMs that accept
r
1
and
r
2
, respectively. An edge with label
a
is added between each final state of
M
1
and each state of
M
2
reached on input
a
from its start state,
s
2
. The final states of
M
2
are final states of
M
,asarethe
final states of
M
1
if
s
2
is a final of
M
2
. It follows that this machine accepts the strings beginning
with a string in
r
1
followed by one in
r
2
.
Search WWH ::
Custom Search