any set that represents the value of the regular expression is called a regular set.

properties of regular sets

property 1. the union of two regular set is regular.

proof −

let us take two regular expressions

re₁ = a(aa)* and re₂ = (aa)*

so, l₁ = {a, aaa, aaaaa,.....} (strings of odd length excluding null)

and l₂ ={ ε, aa, aaaa, aaaaaa,.......} (strings of even length including null)

l₁ ∪ l₂ = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}

(strings of all possible lengths including null)

re (l₁ ∪ l₂) = a* (which is a regular expression itself)

hence, proved.

property 2. the intersection of two regular set is regular.

proof −

let us take two regular expressions

re₁ = a(a*) and re₂ = (aa)*

so, l₁ = { a,aa, aaa, aaaa, ....} (strings of all possible lengths excluding null)

l₂ = { ε, aa, aaaa, aaaaaa,.......} (strings of even length including null)

l₁ ∩ l₂ = { aa, aaaa, aaaaaa,.......} (strings of even length excluding null)

re (l₁ ∩ l₂) = aa(aa)* which is a regular expression itself.

hence, proved.

property 3. the complement of a regular set is regular.

proof −

let us take a regular expression −

re = (aa)*

so, l = {ε, aa, aaaa, aaaaaa, .......} (strings of even length including null)

complement of l is all the strings that is not in l.

so, l’ = {a, aaa, aaaaa, .....} (strings of odd length excluding null)

re (l’) = a(aa)* which is a regular expression itself.

hence, proved.

property 4. the difference of two regular set is regular.

proof −

let us take two regular expressions −

re₁ = a (a*) and re₂ = (aa)*

so, l₁ = {a, aa, aaa, aaaa, ....} (strings of all possible lengths excluding null)

l₂ = { ε, aa, aaaa, aaaaaa,.......} (strings of even length including null)

l₁ – l₂ = {a, aaa, aaaaa, aaaaaaa, ....}

(strings of all odd lengths excluding null)

re (l₁ – l₂) = a (aa)* which is a regular expression.

hence, proved.

property 5. the reversal of a regular set is regular.

proof −

we have to prove l^r is also regular if l is a regular set.

let, l = {01, 10, 11, 10}

re (l) = 01 + 10 + 11 + 10

l^r = {10, 01, 11, 01}

re (l^r) = 01 + 10 + 11 + 10 which is regular

hence, proved.

property 6. the closure of a regular set is regular.

proof −

if l = {a, aaa, aaaaa, .......} (strings of odd length excluding null)

i.e., re (l) = a (aa)*

l* = {a, aa, aaa, aaaa , aaaaa,……………} (strings of all lengths excluding null)

re (l*) = a (a)*

hence, proved.

property 7. the concatenation of two regular sets is regular.

proof −

let re₁ = (0+1)*0 and re₂ = 01(0+1)*

here, l₁ = {0, 00, 10, 000, 010, ......} (set of strings ending in 0)

and l₂ = {01, 010,011,.....} (set of strings beginning with 01)

then, l₁ l₂ = {001,0010,0011,0001,00010,00011,1001,10010,.............}

set of strings containing 001 as a substring which can be represented by an re − (0 + 1)*001(0 + 1)*

hence, proved.

identities related to regular expressions

given r, p, l, q as regular expressions, the following identities hold −

• ∅* = ε
• ε* = ε
• rr* = r*r
• r*r* = r*
• (r*)* = r*
• rr* = r*r
• (pq)*p =p(qp)*
• (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
• r + ∅ = ∅ + r = r (the identity for union)
• r ε = ε r = r (the identity for concatenation)
• ∅ l = l ∅ = ∅ (the annihilator for concatenation)
• r + r = r (idempotent law)
• l (m + n) = lm + ln (left distributive law)
• (m + n) l = ml + nl (right distributive law)
• ε + rr* = ε + r*r = r*