Information Technology Reference
In-Depth Information
It is straightforward to show that the equivalence relations
R
L
and
R
M
are right-invariant.
(See Problems
4.28
and
4.29
.) It is also clear that
R
M
hasasmanyequivalenceclassesasthere
are accessible states of
M
.
Before we present the major results of this section we define a special machine
M
L
that
will be seen to be a minimal machine recognizing the language
L
.
DEFINITION
4.7.5
Given the language
L
over the alphabet
Σ
with finite
R
L
,theDFSM
M
L
=
(Σ
,
Q
L
,
δ
L
,
s
L
,
F
L
)
is defined in terms of the right-invariant equivalence relation
R
L
as follows:
a) the states
Q
L
are the equivalence classes of
R
L
; b) the initial state
s
L
is the equivalence class
[
]
; c) the final states
F
L
are the equivalence classes containing strings in the language
L
;d)foran
arbitrary equivalence class
[
u
]
with representative element
u
Σ
∗
and an arbitrary input letter
∈
a
∈
Σ
, the next-state transition function
δ
L
:
Q
L
×
Σ
→
Q
L
is defined by
δ
L
([
u
]
,
a
)=[
u
a
]
.
For this definition to make sense we must show that condition c) does not contradict the
facts about
R
L
: that an equivalence class containing a string in
L
does not also contain a
string that is not in
L
. But by the definition of
R
L
, if we choose
z
=
,wehavethat
u
R
L
v
only if both
u
and
v
are in
L
. We must also show that the next-state function definition is
consistent: it should not matter which representative of the equivalence class
[
u
]
is used. In
particular, if we denote the class
[
u
]
by
[
v
]
for
v
another member of the class, it should follow
that
[
u
a
]=[
v
a
]
. But this is a consequence of the definition of
R
L
.
Figure
4.20
shows the machine
M
L
associated with
L
=(
10
∗
1
+
0
)
∗
. The initial state
is associated with
[
]
, which is in the language. Thus, the initial state is also a final state. The
state associated with
[
0
]
is also
[
]
because
and 0 are both in
L
. Thus, the transition from state
[
]
on input 0 is back to state
[
]
. Problem
4.31
asks the reader to complete the description of
this machine.
We need the notion of a refinement of an equivalence relation before we establish condi-
tions for a language to be regular.
DEFINITION
4.7.6
An equivalence relation
R
over a set
A
is a
refinement
of an equivalence
relation
S
overthesamesetif
aRb
implies that
aSb
. A refinement
R
of
S
is
strict
if there exist
a
,
b
∈
A
such that
aSb
butitisnottruethat
aRb
.
Over the set
A
=
{
a
,
b
,
c
,
d
}
,therelation
R
=
{{
a
}
{
b
}
{
c
,
d
}}
,
,
is a strict refinement
of the relation
S
=
. Clearly, if
R
is a refinement of
S
,
R
has no fewer
equivalence classes than does
S
. If the refinement
R
of
S
is strict,
R
has more equivalence
classes than does
S
.
{{
a
,
b
}
{
c
,
d
}}
,
1
0
[
]
[
1
]
0
Start
Figure 4.20
The machine
M
L
associated with
L
=(
10
∗
1
+
0
)
∗
.
1
Search WWH ::
Custom Search