What is the equivalence of regular expressions?

Overview

Equivalence is defined as two regular expressions describing or producing the same language.

Assume the regular expressions $S$ and $R$ with language $L$, if $L(S) = L(R)$ then $S = R$.

We can use regular expressions to show whether two languages produce the same strings.

Axioms for equivalence

Equivalence axiomsA proposition regarded as accepted or evidently true. exist for regular expressions. These axioms are similar to propositional logic. The following axioms are defined for the regular expressions $R$, $S$ and $T$. These are as follows:

• The associativity property for union: $S + (R + T)\equiv (S + R) + T$
• The commutativity property for union: $S + R \equiv R + S$
• The associativity property for concatenation: $S \times (R \times T)\equiv (S \times R) \times T$
• The identity property for union: $S + \emptyset \equiv S$
• The identity property for concatenation: $S \times ε \equiv S$
• The left distributivity property: $S (R + T) \equiv SR + ST$
• The right distributivity property:$(S + T) R \equiv SR + TR$
• The idempotence property of Kleene star: $S^{**} \equiv S^*$
• The annihilator property for concatenation: $S \times \emptyset \equiv \emptyset \equiv \emptyset \times S$

Here, the theorem of substitution can also be applied.

The theorem of substitution

Let's assume two substrings, $S$ and $S'$ , are equivalent. Then, if $S$ is a substring of $R$ , replacing $S$ by $S'$ makes a new regular expression equivalent to $R$.

Example

Let's check the equivalency for the following equation:

These proofs are subjective and follow no set logic. We can solve them based on propositional logic. For this example, we will prove that the right-hand side is equal to the left-hand side using axioms.

Let's take the $LHS$:

Use the identity property for concatenation:

Apply the left distributive property:

Use the associative property for concatenation:

Apply the right distributive property:

Use the identity property of concatenation:

Use the substitution property:

This is equal to the right-hand side of the equation. It is to be noted that $L(10(10)^*) \subseteq L((10)^*)$.