Information Technology Reference
In-Depth Information
L
(
M
2
)
L
1
L
2
L
(
M
1
)
Figure 4.1
9
(a) Th
e intersection
L
1
∩
L
2
of two sets
L
1
and
L
2
canbeobtainedbytakingthe
compleme
nt
L
1
∪ L
2
of the union
L
1
∪ L
2
of their complements. (b) If
L
(
M
1
)
⊆ L
(
M
2
)
,then
L
(
M
1
)
∩ L
(
M
2
)=
∅
.
that can recognize the concatenation, union and Kleene closure of regular languages. We now
show that algorithms exist for a number of decision problems concerning finite-state machines.
THEOREM
4.6.2
There are algorithms for each of the following decision problems:
a)
For a finite-state machine
M
and a string
w
, determine if
w
∈
L
(
M
)
.
b)
For a finite-state machine
M
, determine if
L
(
M
)=
∅
.
For a finite-state machine
M
, determine if
L
(
M
)=Σ
∗
.
c)
L
(
M
2
)
.
e) For finite-state machines
M
1
and
M
2
, determine if
L
(
M
1
)=
L
(
M
2
)
.
Proof
To a n s w e r
(
a
)
it suffices to supply
w
to a deterministic finite-state machine equiva-
lent to
M
and observe the final state after it has processed all letters in
w
.Thenumberof
stepsexecutedbythismachineisthelengthof
w
.Question
(
b
)
is answered in Lemma
4.5.2
.
We need only determine if the language contains strings of length less than
m
,where
m
is
the number of states of
M
. This can be done by trying all
inputs
of length less than
m
.
The answer to question
(
c
)
is the same as the answer to
“Is
L
(
M
)=
For finite-state machines
M
1
and
M
2
, determine if
L
(
M
1
)
⊆
d)
∅
?” The answer to
question
(
d
)
is the same as the answer to “Is
L
(
M
1
)
∩
L
(
M
2
)=
∅
?” (See Fig.
4.19
(b).)
Since FSMs that recognize the complement and intersection of regular languages can be
constructed in a finite number of steps (see the proof of Theorem
4.6.1
), we can use the
procedure for
(
b
)
to answer the question. Finally, the answer to question
(
e
)
is “yes” if and
only if
L
(
M
1
)
⊆
L
(
M
2
)
and
L
(
M
2
)
⊆
L
(
M
1
)
.
4.7 State Minimization*
Given a finite-state machine
M
, it is often useful to have a potentially different DFSM
M
min
with the smallest number of states (a minimal-state machine) that recognizes the same language
L
(
M
)
. In this section we develop a procedure to find such a machine recognizing a regular
language
L
. As a step in this direction, we define a natural equivalence relation
R
L
for each lan-
guage
L
and show that
L
is regular if and only if
R
L
has a finite number of equivalence classes.
4.7.1 Equivalence Relations on Languages and States
The relation
R
L
is used to define a machine
M
L
.When
L
is regular, we show that
M
L
is a
minimal-state DFSM. We also give an explicit procedure to construct a minimal-state DFSM
Search WWH ::
Custom Search