Information Technology Reference
In-Depth Information
2
m
and we apply the pumping
lemma to it to find another shorter string that is also in
L
, contradicting the hypothesis that
it was the shortest string of length greater than or equal to 2
m
.
|
w
|≥
In the first case, we are done. In the second case,
4.6 Properties of Regular Languages
Section
4.4
established the equivalence of regular languages (recognized by finite-state ma-
chines) and the languages denoted by regular expressions. We now present properties satisfied
by regular languages. We say that
a class of languages is closed under an operation
if ap-
plying that operation to a language (or languages) in the class produces another language in
the class. For example, as shown below, the union of two regular languages is another regular
language. Similarly, the Kleene closure applied to a regular language returns another regular
language.
Given a language
L
over an alphabet
Σ
,
the complement of L
is the set
L
=Σ
∗
−
L
,
the strings that are in
Σ
∗
but not in
L
. (This is also called the
difference
between
Σ
∗
and
L
.)
The
intersection
of two languages
L
1
and
L
2
, denoted
L
1
∩
L
2
, is the set of strings that are
in both languages.
THEOREM
4.6.1
The class of regular languages is closed under the following operations:
•
concatenation
•
union
•
Kleene closure
•
complementation
•
intersection
Proof
In Section
4.4
we showed that the languages denoted by regular expressions are ex-
actly the languages recognized by finite-state machines (deterministic or nondeterministic).
Since regular expressions are defined in terms of concatenation, union, and Kleene closure,
they are closed under each of these operations.
The proof of closure of regular languages under complementation is straightforward. If
L
is regular and has an associated FSM
M
that recognizes it, make all final states of
M
non-
final and all
no
n-final states final. This new machine then recognizes exactly the complement
of
L
.Thus,
L
is also regular.
The proof of closure of regular languages under intersection follows by noting that if
L
1
and
L
2
are regular languages, then
L
1
∩
L
2
=
L
1
∪
L
2
that is, the intersection of t
wo
sets
can
be obtained by complementing the union
of
th
eir
complements. Since each of
L
1
and
L
2
is regular, as is their union, it follows that
L
1
∪
L
2
is regular. (See Fig.
4.19
(a).) Finally, the complement of a regular set is regular.
When we come to study Turing machines in Chapter
5
, we will show that there are well-
defined languages that have no machine to recognize them, even if the machine has an infinite
amount of storage available. Thus, it is interesting to ask if there are algorithms that solve
certain decision problems about regular languages in a finite number of steps. (Machines that
halt on all input are said to
implement algorithms
.) As shown above, there are algorithms
Search WWH ::
Custom Search