Algebraic Laws of Regular
Expressions
Finite Automata Theory
& Formal Languages
Khawaja 2022 Automata Theory & Languages 1
Algebraic Laws of Regular Expressions
• Like arithmetic expressions, the regular expressions have a
number of laws.
• If we think of union as addition and concatenation as
multiplication, many of these are similar to the laws for
arithmetic.
• However, there are a few places where the analogy breaks down.
• There are also some laws that apply to regular expressions but
have no analogy for arithmetic.
Khawaja 2022 Automata Theory & Languages 2
Associativity and Commutativity
• Commutativity is the property of an operator that says we can switch
the order of its operands and get the same result.
An example for arithmetic addition is:
x+y = y+x
• Associativity is the property of an operator that allows us to regroup
the operands when the operator is applied twice.
An example for arithmetic multiplication is:
(x * y) * z = x * (y * z)
Khawaja 2022 Automata Theory & Languages 3
Associativity and Commutativity (ctd)
The laws of these types that hold for regular expressions:
• L+M=M+L
This law, the commutative law for union says that we may take the union of two
languages in either order.
For example, if L = {01, 0}, M = {10, 11}, N = {00, 1}
L + M = {0, 01, 10, 11}, which is same as M + L
• (L + M) + N = L + (M + N)
This law, the associative law for union says that we may take the union of three
languages either by taking the union of the first two initially, or taking the union of
the last two initially.
Using same sample languages, (L + M) + N = {0, 1, 00, 01, 10, 11}, which is same as L
+ (M + N)
Khawaja 2022 Automata Theory & Languages 4
Associativity and Commutativity (ctd)
• (LM)N = L(MN)
This law, the associative law for concatenation, says that we can
concatenate three languages by concatenating either the first two or the
last two initially.
• Missing from this list is the law LM = ML, which would say that
concatenation is commutative. However, this law is false.
L = {01, 0}, M = {10, 11}, N = {00, 1}
L.M = {0110, 0111, 010, 011}
M.L = {1001, 100, 1101, 110}
Khawaja 2022 Automata Theory & Languages 5
Identities and Annihilators
• An identity for an operator is a value such that when the operator is
applied to the identity and some other value, the result is the other
value. For instance in arithmetic:
– 0 is the identity for addition, since 0 + x = x + 0 = x
– 1 is the identity for multiplication, since 1 * x = x * 1 = x
• An annihilator for an operator is a value such that when the operator
is applied to the annihilator and some other value, the result is the
annihilator. For instance in arithmetic:
– 0 is an annihilator for multiplication, since 0 * x = x * 0 = 0
– There is no annihilator for addition.
Khawaja 2022 Automata Theory & Languages 6
Identities and Annihilators (ctd)
There are three laws for regular expressions involving these concepts :
• Ф+L=L+Ф=L
This law asserts that Ф is the identity for union.
• εL = Lε = L
This law asserts that ε is the identity for concatenation
• ФL=LФ=Ф
This law asserts that Ф is the annihilator for concatenation
L = {01, 0}, M = {10, 11}, N = {00, 1}, Ф = { }
LФ = { } = Ф
Khawaja 2022 Automata Theory & Languages 7
Identities and Annihilators (ctd)
• If we have union of several expressions, some of which are simplified
to Ф, then Ф’s can be dropped. L1 + Ф + L2 + Ф + L3 = L1 + L2 + L3
• If we have concatenation of several expressions, some of which are ε,
we can drop the ε’s L1.ε.L2.ε.L3 = L1.L2.L3
• If we have concatenation of any number of expressions, if even one of
them is Ф, then the entire concatenation can be replaced by Ф.
L1.Ф.L2.Ф.L3 = Ф
Ф={}
ε = empty string = “”
“010” . ”” = “010”
Khawaja 2022 Automata Theory & Languages 8
Distributive Laws
• From arithmetic, distributive law of multiplication over addition is:
x (y + z) = xy + xz
• Since concatenation is not commutative in regular expressions,
there are two laws:
1. L (M + N) = LM + LN
Left distributive law of concatenation over union
2. (M + N) L = ML + NL
Right distributive law of concatenation over union
Khawaja 2022 Automata Theory & Languages 9
Idempotent Law
• An operator is said to be idempotent if the result of applying it to
two of the same values as arguments is that value.
• In Regular Expressions, union and intersection are idempotent
operators.
1. L + L = L
The union of two identical expressions, can be replaced by one copy of the
expression.
L = {01, 0}
L + L = {01, 0} U {01, 0} = {01, 0} = L
Khawaja 2022 Automata Theory & Languages 10
Laws Involving Closure
1. (L*)* = L*
Closing an expression that is already closed does not change the
language.
L = {01, 0}, L = {01, 0}
2. Ф* = ε LUL = L
Closure of Ф contains only the string ε since L.L = {0101, 010, 001, 00}
L(Ф*) = ε U L(Ф) U L(Ф)L(Ф) U L(Ф)L(Ф)L(Ф) U … L(Ø) = { }
L(Ø).L(Ø) = { } = Ø
L = ε, L = L
0 1
L(Ø).L(Ø).L(Ø) = { } = Ø
3. ε* = ε
Concatenating any number of copies of the empty string is the
empty string itself.
Khawaja 2022 Automata Theory & Languages 11
Laws Involving Closure (ctd)
4. L+ = LL* = L*L
since L+ = L + LL + LLL + …
and L* = ε + L + LL + LLL + …
Note: + means one or more occurrences and ? means zero or one
occurrence.
5. L* = L+ + ε
6. L? = ε + L (? means zero or one occurrence of the language)
This rule is actually the definition of ? Operator.
Khawaja 2022 Automata Theory & Languages 12
Discovering Laws of Regular Expressions
• There is an infinite variety of laws about regular expressions that
might be proposed.
• One such proposed law is:
(L + M)* = (L* M*)*
Khawaja 2022 Automata Theory & Languages 13
