Information Technology Reference
In-Depth Information
R
(
0
)
i
,
j
is formally defined below.
=
{
a
|
δ
(
q
i
,
a
)=
q
j
}
if
i
=
j
R
(
0
)
i
,
j
{
a
|
δ
(
q
i
,
a
)=
q
j
}∪{
}
if
i
=
j
Since
R
(
k
)
i
,
j
is defined as the set of strings that take
M
from
q
i
to
q
j
without passing through
states outside of
Q
(
k
)
, it can be recursively defined as the strings that take
M
from
q
i
to
q
j
without passing through states outside of
Q
(
k−
1
)
plus those that take
M
from
q
i
to
q
k
without passing through states outside of
Q
(
k−
1
)
, followed by strings that take
M
from
q
k
to
q
k
zero or more times without passing through states outside
Q
(
k−
1
)
, followed by
strings that take
M
from
q
k
to
q
j
without passing through states outside of
Q
(
k−
1
)
.Thisis
represented by the formula below and suggested in Fig.
4.17
:
R
(
k−
1
)
k
,
k
∗
R
(
k
)
i
,
j
=
R
(
k−
1
)
i
,
j
R
(
k−
1
)
i
,
k
R
(
k−
1
)
k
,
j
∪
·
·
It follows by induction on
k
that
R
(
k
)
i
,
j
correctly describes the strings that take
M
from
q
i
to
q
j
without passing through states of index higher than
k
.
We now exhibit the set
r
(
k
)
R
(
k
)
{
i
,
j
}
of regular expressions that describe the sets
{
i
,
j
|
1
≤
and establish the correspondence by induction. If the set
R
(
0
)
i
,
j
i
,
j
,
k
≤
m
}
contains the
letters
x
1
,
x
2
,
...
,
x
l
(which might include the empty letter
), then we let
r
(
0
)
=
x
1
+
x
2
+
i
,
j
+
x
l
. Assume that
r
(
k−
1
)
correctly describes
R
(
k−
1
)
i
,
j
···
. It follows that the regular expression
i
,
j
r
(
k−
1
)
k
,
k
∗
r
(
k−
1
)
k
,
j
r
(
k
)
i
,
j
=
r
(
k−
1
)
+
r
(
k−
1
)
i
,
k
(4.1)
i
,
j
correctly describes
R
(
k
)
i
,
j
. This concludes the proof.
The dynamic programming algorithm given in the above proof is illustrated by the DFSM
in Fig.
4.15
. Because this algorithm can produce complex regular expressions even for small
DFSMs, we display almost all of its steps, stopping when it is obvious which results are needed
for the regular expression that describes the strings recognized by the DFSM. For 1
≤
k
≤
6,
R
(
k−
1
)
i
,
j
R
(
k−
1
)
i
,
k
R
(
k−
1
)
k
,
j
R
(
k−
1
)
k
,
k
Figure 4.17
A recursive decomposition of the set
R
(
k
)
i
,
j
of strings that cause an FSM to move
from state
q
i
to
q
j
without passing through states
q
l
for
l>k
.
Search WWH ::
Custom Search