language is not regular.
In this chapter, we look at a variety of properties of regular languages. These
properties tell us a great deal about what regular languages can and cannot do.
Later, when we look at the same questions for other language families,
similarities and differences in these properties will allow us to contrast the
various language families.
4.1 Closure Properties of Regular Languages
Consider the following question: Given two regular languages L 1 and L 2 , is their
union also regular? In specific instances, the answer may be obvious, but here
we want to address the problem in general. Is it true for all regular L 1 and L 2 ? It
turns out that the answer is yes, a fact we express by saying that the family of
regular languages is closed under union. We can ask similar questions about
other types of operation son languages; this leads us to the study of the closure
properties of languages in general.
Closure properties of various language families under different operations
are of considerable theoretical interest. At first sight, it may not be clear what
practical significance these properties have. Admittedly, some of them have very
little, but many results are useful. By giving us insight into the general nature of
language families, closure properties help us answer other, more practical
questions. We will see instances of this (Theorem 4.7 and Example 4.13) later in
this chapter.
Closure under Simple Set Operations
We begin by looking at the closure of regular languages under the common set
operations, such as union and intersection.
Theorem 4.1
If L 1 and L 2 are regular languages, then so are L 1 ∪ L 2 , L 1 ∩ L 2 , L 1 L 2 ,
, and
. We say that the family of regular languages is closed under union,
intersection, concatenation, complementation, and star-closure.
In this chapter, we look at a variety of properties of regular languages. These
properties tell us a great deal about what regular languages can and cannot do.
Later, when we look at the same questions for other language families,
similarities and differences in these properties will allow us to contrast the
various language families.
4.1 Closure Properties of Regular Languages
Consider the following question: Given two regular languages L 1 and L 2 , is their
union also regular? In specific instances, the answer may be obvious, but here
we want to address the problem in general. Is it true for all regular L 1 and L 2 ? It
turns out that the answer is yes, a fact we express by saying that the family of
regular languages is closed under union. We can ask similar questions about
other types of operation son languages; this leads us to the study of the closure
properties of languages in general.
Closure properties of various language families under different operations
are of considerable theoretical interest. At first sight, it may not be clear what
practical significance these properties have. Admittedly, some of them have very
little, but many results are useful. By giving us insight into the general nature of
language families, closure properties help us answer other, more practical
questions. We will see instances of this (Theorem 4.7 and Example 4.13) later in
this chapter.
Closure under Simple Set Operations
We begin by looking at the closure of regular languages under the common set
operations, such as union and intersection.
Theorem 4.1
If L 1 and L 2 are regular languages, then so are L 1 ∪ L 2 , L 1 ∩ L 2 , L 1 L 2 ,
, and
. We say that the family of regular languages is closed under union,
intersection, concatenation, complementation, and star-closure.