Information Technology Reference
In-Depth Information
1
1
q
2
q
4
0
0
Start
0
0
q
1
q
5
1
q
3
1
0, 1
Figure 4.15
The DFSM of Figure
4.3
with a relabeling of states.
Proof
Let
Q
=
be the final states. The
proof idea is the following. For every pair of states
(
q
i
,
q
j
)
of
M
we construct a regular
expression
r
(
0
)
{
q
1
,
q
2
,
...
,
q
n
}
and
F
=
{
q
j
1
,
q
j
2
,
...
,
q
j
p
}
denoting the set
R
(
0
)
i
,
j
containing input letters that take
M
from
q
i
to
q
j
without passing through any other states. If
i
=
j
,
R
(
0
)
i
,
j
i
,
j
contains the empty letter
because
M
can move from
q
i
to
q
i
without reading an input letter. (These definitions are illustrated
in the table
T
(
0
)
of Fig.
4.16
.) For
k
=
1, 2,
...
,
m
we proceed to define the set
R
(
k
)
i
,
j
of
strings that take
M
from
q
i
to
q
j
without passing through any state except possibly one in
Q
(
k
)
=
. We also associate a regular expression
r
(
k
)
i
,
j
with the set
R
(
k
)
i
,
j
.Since
Q
(
n
)
=
Q
, the input strings that carry
M
from
s
=
q
t
, the initial state, to a final state in
F
are the strings accepted by
M
. They can be described by the following regular expression:
{
q
1
,
q
2
,
...
,
q
k
}
r
(
n
)
t
,
j
1
+
r
(
n
)
+
r
(
n
)
t
,
j
p
t
,
j
2
+
···
This method of proof provides a
dynamic programming
algorithm to construct a reg-
ular expression for
L
.
r
(
0
)
i
,
j
T
(
0
)
=
{
}
i
\
j
1
2
3
4
5
∅
∅
1
0
1
2
∅
0
1
∅
3
∅
∅
+0+1
∅
∅
∅
∅
4
1
0
5
∅
0
∅
1
Figure 4.16
The table
T
(
0
)
containing the regular expressions
{r
(
0
)
i
,
j
}
associated with the DFSM
inshowninFig.
4.15
.
Search WWH ::
Custom Search