Identity Rules of Regular Expressions

For Complete YouTube Video: Click Here

In this class, We discuss Identity Rules of Regular Expressions.

The reader should have prior knowledge of regular expressions and their operators. Click Here.

First, we need to understand the empty set.

A language consists of no strings. We call it an empty set.

The symbol to represent an empty set is Φ or {}.

Point to understand: epsilon is different from the empty set.

If a language accepts epsilon means without taking input, we can accept.

Identity Rules

I1: Φ + A = A

What is A?

It is a language. Or consider it as a regular expression.

We write regular expressions for a language.

From the definition of the union: 

A + B is a set of strings from either A or B or Both.

If B = Φ, then A

I2: Φ A = Φ

From the definition of concatenation: 

A.B means a set of strings of ab where a belongs to A and b belongs to B.

When B is Φ, we do not have the possible choice to take a string from B.

So A Φ = Φ

I3: εA = Aε = A

We concatenate any string with epsilon. We get the string itself.

I4: ε* = ε and Φ * = ε

What is star?

We take any string from the language or nothing from the language.

We take any string any number of times. This is what star operator means.

The language consists only of ε.

We take epsilon anynumber of times we get epsilon.

Similarly, take any string from Φ. There are no strings.

Take nothing from Φ we get epsilon.

I5: A + A = A

I6: A*A* = A*

Whatever we write using A* we can repeat. so we can take A*A* = A*

I7: AA* = A*A

Take A = {1}

AA* = {1, 11, . . .}

The same strings can be generated by using A*A.

I8: (A*)* = A*

Closing an expression which is already closed does not change.

L = {1, 01}

L* = {ε, 1, 01, 101, . . . }

(L*)* = {1, 01, 01101, . , .}

01101 is obtained by third and fourth string from L*.

The string 01101 string can be generated using L*. because 01, and 101 are taken by the strings from L*.

I9: (ε + AA*) = A*

Take A = {1}

(ε + 11*) can generate epsilon, a single one, and any number of ones.

We can write it as 1*.

I10: (pq)*p = p(qp)*

Take p = a and q = b

(ab)*a = a(ba)*

Both expressions can generate the same strings

εa = aε

aba = aba

Similarly, same strings can be generated.

I11: (p + q)* = (p*q*)* = (p* + q*)*

The expressions mentioned above will generate the same strings.

I12: (P + Q)R = PR + QR