Regular language

Definition of Regular Language

A Regular language whose regular expressions can be drawn is known as regular language.

Property of Regular Language:

  • Closure Property:

If L and M are two languages then LM is also a regular language such as L*.

  • Concatenation:

The concatenation property over language L and M also exist as a property.

  • Union:

The union property can be stated as if we have two regular expressions such as ab* and abb* then the union property between them can be written as ab* + abb*.

For example

L = {b, bbb, bbbbb …} (Strings of odd length excluding Null)

M = {ε, bb, bbbb, bbbbbb …} (Strings of even length including Null).

L ∪ M = {ε, b, bb, bbbb, bbbb, bbbbb, bbbbbb …}.

Strings of all possible lengths including Null.

RE (L ∪ M) = b* (which is a regular expression itself).

  • Intersection:

The intersection property can also exist but specific conditions such as L∩M can be possible or maybe not possible.

So, L = {b, bb, bbbb, bbbb…} (Strings of all possible lengths excluding Null).

M = {ε bb, bbbb, bbbbbb…} (Strings of even length including Null).

L ∩ M = {bb, bbbb, bbbbbb…} (Strings of even length excluding Null).

RE (L ∩ M) = bb (bb)* which is a regular expression itself.

Proof by De Morgan’s Law

(L∩M)ᴄ = LᴄMᴄ

Lᴄ = U-L is a regular language, therefore,

L-M = L∩Mᴄ can be said.

  • Reverse OR Inverse Property:

LR can be a regular language in the case of inverse language.

We have to prove LR is also regular if L is a regular set.

Let, L = {01, 10, 11, 10}

RE (L) = 01 + 10 + 11 + 10

LR = {10, 01, 11, 01}

RE (LR) = 01 + 10 + 11 + 10 which is regular.

Regular expression


We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.

Leave a Reply