Information Technology Reference
In-Depth Information
recognizing a regular language
L
. The approach is the following: a) given a regular expression,
an NFSM is constructed (Theorem
4.4.1
); b) an equivalent DFSM is then produced (Theo-
rem
4.2.1
); c) equivalent states of this DFSM are discovered and coalesced, thereby producing
the minimal machine. We begin our treatment with a discussion of equivalence relations.
DEFINITION
4.7.1
An
equivalence relation
R
on a set
A
is a partition of the elements of
A
into
disjoint subsets called
equivalence classes
. If two elements
a
and
b
are in the same equivalence
class under relation
R
,wewrite
aRb
.If
a
is an element of an equivalence class, we represent its
equivalence class by
[
a
]
. An equivalence relation is represented by its equivalence classes.
An example of equivalence relation on the set
A
=
{
}
0, 1, 2, 3
is the set of equivalence
{{
}
{
}}
.Then,
[
0
]
and
[
2
]
denote the same equivalence class, namely
{
}
classes
0, 2
,
1, 3
0, 2
,
whereas
[
1
]
and
[
2
]
denote different equivalence classes.
Equivalence relations can be defined on any set, including the set of strings over a finite
alphabet (a language). For example, let the partition
0
∗
,0
(
0
∗
10
∗
)
+
,1
(
0
+
1
)
∗
}
of the
set
(
0
+
1
)
∗
denote the equivalence relation
R
. The equivalence classes consist of strings
containing zero or more 0's, strings starting with 0 and containing at least one 1, and strings
beginning with 1. It follows that 00
R
000 and 1001
R
11 but not that 10
R
01.
Additional conditions can be put on equivalence relations on languages. An important
restriction is that an equivalence relation be right-invariant (with respect to concatenation).
{
DEFINITION
4.7.2
An equivalence relation
R
over the alphabet
Σ
is
right-invariant
(with respect
to concatenation) if
for all
u
and
v
in
Σ
∗
,
u
R
v
implies
uz
R
vz
for all
z
Σ
∗
.
∈
.Thatis,
R
consists of two equiv-
alence classes, the set containing strings with an even number of 1's and the set containing
strings with an odd number of 1's.
R
is right-invariant because if
u
R
v
; that is, if the numbers
of 1's in
u
and
v
are both even or both odd, then the same is true of
uz
and
vz
for each
z
For example, let
R
=
{
(
10
∗
1
+
0
)
∗
,0
∗
1
(
10
∗
1
+
0
)
∗
}
Σ
∗
,thatis,
uz
R
vz
.
To each language
L
, whether regular or not, we associate the natural equivalence relation
R
L
defined below. Problem
4.30
shows that for some languages
R
L
has an unbounded number
of equivalence classes.
∈
DEFINITION
4.7.3
Given a language
L
over
Σ
, the equivalence relation
R
L
is defined as follows:
strings
u
,
v
Σ
∗
are equivalent, that is,
u
R
L
v
,ifandonlyif foreach
z
Σ
∗
,eitherboth
uz
∈
∈
and
vz
are in
L
or both are not in
L
.
(
10
∗
1
+
0
)
∗
,0
∗
1
(
10
∗
1
+
0
)
∗
}
The equivalence relation
R
=
{
given above is the equivalence
relation
R
L
for both the language
L
=
(
10
∗
1
+
0
)
∗
and the language
L
=0
∗
1
(
10
∗
1
+
0
)
∗
.
A natural right-invariant equivalence relation on strings can also be associated with each
DFSM, as shown below. This relation defines two strings as equivalent if they carry the ma-
chine from its initial state to the same state. Thus, for each state there is an equivalence class
ofstringsthattakethemachinetothatstate.Forthispurposeweextendthestatetransition
function
δ
to strings
a
Σ
∗
recursively by
δ
(
q
,
)=
q
and
δ
(
q
,
σ
a
)=
δ
(
δ
(
q
,
σ
)
,
a
)
for
∈
σ
∈
Σ
.
DEFINITION
4.7.4
Given a DFSM
M
=(Σ
,
Q
,
δ
,
s
,
F
)
,
R
M
is the equivalence relation defined
as follows: for all
u
,
v
Σ
∗
,
u
R
M
v
if and only if
δ
(
s
,
u
)=
δ
(
s
,
v
)
. (Note that
δ
(
q
,
)=
q
.)
∈
Search WWH ::
Custom Search