Information Technology Reference
In-Depth Information
0
q
3
s
3
0
Start
0
s
0
1
1
0
q
2
q
f
s
2
Figure 4.13
A nondeterministic machine accepting 10
∗
+
0.
state of
M
0
, the machine accepting
r
4
. (The state
s
1
is marked as inaccessible.) Figure
4.12
(page
163
) shows an NFSM accepting
r
1
r
2
constructed by
concatenating
the machine
M
1
accepting
r
1
with
M
2
accepting
r
2
.(
s
1
is inaccessible.) Figure
4.13
gives an NFSM accepting
the language denoted by
r
1
r
2
+
r
3
, designed by forming the
union
of machines for
r
1
r
2
and
r
3
.
(States
s
2
and
s
3
are inaccessible.) Figure
4.14
shows a DFSM recognizing the same language
as that accepted by the machine in Fig.
4.13
.Herewehaveaddedarejectstate
q
R
to which all
states move on input letters for which no state transition is defined.
4.4.2 Regular Expressions Describing FSM Languages
We now give the second part of the proof of equivalence of FSMs and regular expressions. We
show that every language recognized by a DFSM can be described by a regular expression. We
illustrate the proof using the DFSM of Fig.
4.3
, which is the DFSM given in Fig.
4.15
except
for a relabeling of states.
THEOREM
4.4.2
If the language
L
is recognized by a DFSM
M
=(Σ
,
Q
,
δ
,
s
,
F
)
,then
L
can
be represented by a regular expression.
0, 1
0, 1
q
3
q
R
0
Start
1
s
0
1
0
1
0
q
2
q
1
Figure 4.14
A deterministic machine accepting 10
∗
+
0.
Search WWH ::
Custom Search