Regular Language

Properties of Regular Language



Subjects to be Learned

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