Regular Language
Properties of Regular Language
Subjects to be Learned
- Closure of the set of regular languages under union, concatenation
and Kleene star operations.
- Regularity of finite languages
Contents
Here we are going to learn two of the properties of regular languages.
We will see more properties later.
To review definition of regular language
click here
We say a set of languages is closed
under an operation if the result of
applying the operation to any arbitrary language(s) of the set is a language
in the set.
For example a set of languages is closed under union if the union of any two languages
of the set also belongs to the set.
The following theorem is immediate from the Inductive Clause of the definition of
the set of regular
languages.
Theorem 1: The set of regular languages over an alphabet
is closed under operations union,
concatenation
and Kleene star.
Proof: Let Lr and Ls be regular languages
over an alphabet . Then by the definition of
the set of regular languages ,
Lr
Ls ,
LrLs
and Lr*
are regular languages and they are obviously over the alphabet .
Thus the set of regular languages is closed under those operations.
Note 1: Later we shall see that the complement of a regular language and the intersection of
regular laguages are also regular.
Note 2: The union of infinitely many regular languages is not necessarily regular.
For example
while { akbk } is regular for any natural number k ,
{ anbn | n is a natural number } which is
the union of all the languages { akbk } , is not regular
as we shall see later.
The following theorem shows that any finite language is regular.
We say a language is finite if it consists of a finite number of strings,
that is, a finite language is a set of n strings
for some natural number n.
Theorem 2: A finite language is regular.
Proof: Let us first assume that a language consisting of a single string is regular
and prove the theorem by induction. We then prove that a language consisting of a single string is regular.
Claim 1: A language consisting of n strings is regular for any natural number n
(that is, a finite language is regular) if { w } is regular for any string w.
Proof of the Claim 1: Proof by induction on the number of strings.
Basis Step: (corresponding to n = 0) is a regular language
by the Basis Clause of the
definition
of
regular language.
Inductive Step: Assume that a language L consisting of n strings is a regular language (induction hypothesis).
Then since { w } is a regular language
as proven below, L { w } is a regular language
by the
definition
of
regular language.
End of proof of Claim 1
Thus if we can show that { w } is a regular language for any string w, then we have proven
the theorem.
Claim 2: Let w be a string over an alphabet .
Then { w } is a regular language.
Proof of Claim 2: Proof by induction on strings.
Basis Step: By the Basis Clause of the
definition of
regular language,
{} and { a } are regular languages for
any arbitrary symbol a of .
Inductive Step: Assume that { w } is a regular language for an arbitrary string w
over . Then for any symbol a of ,
{ a } is a regular language from the Basis Step. Hence by the Inductive Clause of the
definition
of regular language
{ a }{ w } is regular. Hence { aw } is regular.
End of proof for Claim 2
Note that Claim 2 can also be proven by induction on the length of string.
End of proof of Theorem 2.
Test Your Understanding of Properties of Regular Language
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
In the questions below the following notations are used:
a^i for ai , etc.
\Sigma for
\cup for
<= for
Next -- Introduction to Finite Automata
Back to Study Schedule
Back to Table of Contents