Home » Theory of Computation

Regular sets and their properties in Theory of Computation

Here, we are going to learn about the regular sets and their properties in theory of computation. By Mahak Jain, on November 14, 2018

Regular sets

Any set that denotes the value of the Regular Expression is called a "Regular Set".

Properties of regular sets

Regular sets have various properties:

Property 1: The union of two regular sets is also a regular set

Proof:

Let there be two regular expressions
RE1 = 0(00)* and RE2 = (00)*
So, L1 = {0, 000, 00000,..} (odd length strings without Null)
and L2 ={ ε, 00, 0000, 000000,.......} (even length stringswith Null)
L1 ∪ L2 = { ε, 0, 00, 000, 0000, 00000, 000000,.......}
(all possible lengths stringswith Null)
RE (L1 ∪ L2) = 0* (this is also a regular expression or a regular set)

Hence, proved.

Property 2: The intersection of two regular set is also a regular set

Proof:

Let there be two regular expressions
RE1 = 0(0*) and RE2 = (00)*
So, L1 = { 0,00, 000, 0000, ....} (odd length strings without Null)
L2 = { ε, 00, 0000, 000000,.......} (even length strings with Null)
L1 ∩ L2 = { 00, 0000, 000000,.......} (even length stringswithout Null)
RE (L1 ∩ L2) = 00(00)*(this is a regular set or regular expression also).

Hence, proved.

Property 3: The complement of a regular set is also regular set

Proof:

Let there be a regular expression −
RE = (00)*
So, L = {ε, 00, 0000, 000000, .......} (even length stringswith Null)
Complement of L is set of all the strings that is not included in L.
So, L' = {0, 000, 00000, .....} (odd length stringswithout Null)
RE (L') = 0(00)*this denotes a regular set or regular expression in itself.

Hence, proved.

Property 4: The difference of two regular set is also a regular set

Proof:

Let there be two regular expressions −
RE1 = 0 (0*) and RE2 = (00)*
So, L1 = {0, 00, 000, 0000, ....} (all possible lengths stringswithout Null)
L2 = { ε, 00, 0000, 000000,.......} (even length strings with Null)
L1 – L2 = {0, 000, 00000, 0000000, ....}
(all odd lengths strings without Null)
RE (L1 – L2) = 0 (00)*(this is also a regular set or a 
regular expression in itself)

Hence, proved.

Property 5: The reversal of a regular set is also a regular set

Proof:

If L is a regular set:
Let, L = {ab, ba, bb, ba}
RE (L) = b1 + 1b +bb + ba
LR = {ba, ab, bb, ab}
RE (LR) = ab + ba + bb + bathis is the reverse and also a regular 
set or a regular expression in itself 

Hence, proved.

Property 6: The closure of a regular set or an expression is also a regular set

Proof:

If L = {0, 000, 00000, .......} (all odd length strings without Null)
i.e., RE (L) = 0 (00)*
L* = {0, 00, 000, 0000 ,00000,……………} ( all lengths strings without Null)
RE (L*) = 0 (0)*(this is also a regular set or a regular expression) 

Hence, proved.

Property 7: The concatenation of two regular sets is also a regular set

Proof:

Let RE1 = (a+1)*a and RE2 = a1(a+1)*
Here, L1 = {a, aa, 1a, aaa, a1a, ......} (Set of strings ending in a)
and L2 = {a1, a1a,a11,.....} (Set of strings beginning with a1)
Then, L1 L2 = {aa1,aa1a,aa11,aaa1,aa1a,aaa11,1aa1,1aa1a,.............}
Set of strings containing aa1 as a substring which 
can be denoted by an RE − (a + 1)*aa1(a + 1)*

Hence, proved.