Regular language

  • Post author:
Download PDF

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