W
Chapter 4
Properties of
Regular Languages
e have defined regular languages, studied some ways in which they
can be represented, and have seen a few examples of their
usefulness. We now raise the question of how general regular
languages are. Could it be that every formal language is regular?
Perhaps any set can be accepted by some, albeit very complex,
finite automaton. As we will see shortly, the answer to this conjecture is
definitely no. But to understand why this is so, we must inquire more deeply into
the nature of regular languages and see what properties the whole family has.
The first question we raise is what happens when we perform operations on
regular languages. The operations we consider are simple set operations, such as
concatenation, as well as operations in which each string of a language is
changed, as for instance in Exercise 24, Section 2.1. Is the resulting language
still regular? We refer to this as a closure question. Closure properties, although
mostly of theoretical interest, help us in discriminating between the various
language families we will encounter.
A second set of questions about language families deals with our ability to
decide on certain properties. For example, can we tell whether a language is
finite or not? As we will see, such questions are readily answered for regular
languages, but are not as easy for other language families.
Finally we consider the important question: How can we tell whether a given
language is regular or not? If the language is in fact regular, we can always show
it by giving some dfa, regular expression, or regular grammar for it. But if it is
not, we need another line of attack. One way to show a language is not regular is
to study the general properties of regular languages, that is, characteristics that
are shared by all regular languages. If we know of some such property, and if we
can show that the candidate language does not have it, then we can tell that the
Chapter 4
Properties of
Regular Languages
e have defined regular languages, studied some ways in which they
can be represented, and have seen a few examples of their
usefulness. We now raise the question of how general regular
languages are. Could it be that every formal language is regular?
Perhaps any set can be accepted by some, albeit very complex,
finite automaton. As we will see shortly, the answer to this conjecture is
definitely no. But to understand why this is so, we must inquire more deeply into
the nature of regular languages and see what properties the whole family has.
The first question we raise is what happens when we perform operations on
regular languages. The operations we consider are simple set operations, such as
concatenation, as well as operations in which each string of a language is
changed, as for instance in Exercise 24, Section 2.1. Is the resulting language
still regular? We refer to this as a closure question. Closure properties, although
mostly of theoretical interest, help us in discriminating between the various
language families we will encounter.
A second set of questions about language families deals with our ability to
decide on certain properties. For example, can we tell whether a language is
finite or not? As we will see, such questions are readily answered for regular
languages, but are not as easy for other language families.
Finally we consider the important question: How can we tell whether a given
language is regular or not? If the language is in fact regular, we can always show
it by giving some dfa, regular expression, or regular grammar for it. But if it is
not, we need another line of attack. One way to show a language is not regular is
to study the general properties of regular languages, that is, characteristics that
are shared by all regular languages. If we know of some such property, and if we
can show that the candidate language does not have it, then we can tell that the