Regular Expression
(Part 2)
LECTURER: JAY A. ABALETA
• Commutative:
• E+F = F+E
Algebraic • Associative:
• (E+F)+G = E+(F+G)
Laws of • (EF)G = E(FG)
Regular • Identity:
• E+Φ = E
Expressions • E=E=E
• Annihilator:
• ΦE = EΦ = Φ
2
Annihilator
Φ typically represents
𝐸 is a general linear
the zero element
(e.g., the zero vector
in a vector space, or operator or matrix.
the zero function in a
space of functions).
Example: Zero vector in a vector space
• multiplying the matrix 𝐸 by the zero vector Φ results in
Φ again, verifying 𝐸Φ=Φ.
• Distributive:
• E(F+G) = EF + EG
• (F+G)E = FE+GE
• Idempotent: E + E = E
Algebraic • Involving Kleene closures:
• (E*)* = E*
Laws… • Φ* =
• * =
• E+ =EE*
• E? = +E
5
1. {0,1,2}
R=0+1+2
2. {ε, ab}
Describing R = ε ab
3. {abb, a, b, bba}
Regular R = abb + a + b + bba
Expression 4. {ε, 0, 00, 000, 0000,…..}
R = 0*
5. {1, 11, 111, 1111,…..}
R = 1+
Identities of
Regular
Expression
Identity for Union
Identity: 𝑟∪∅=𝑟
Where: The union of a regular expression 𝑟 with the
empty set (∅) is just 𝑟, since the empty set does not
match any strings.
Example:𝑎∪∅=𝑎
The expression a ∪ ∅ is equivalent to just a.
Empty String (𝜀)
Identity for Concatenation with the
Identity: 𝑟𝜀=𝜀𝑟=𝑟
Where: Concatenating any regular expression 𝑟 with
since 𝜀 represents the empty string, which doesn't
the empty string (𝜀) does not change the expression,
affect other strings in concatenation.
Example:𝑎𝜀=𝑎
The expression aε is equivalent to just a.
Identity for Kleene Star
Identity 1: 𝑟∗ = 𝜀 ∪ 𝑟𝑟∗
Where: The Kleene star of a regular expression 𝑟 means
zero or more occurrences of 𝑟. This can be expressed as
either the empty string (𝜀) or one occurrence of 𝑟
followed by more occurrences of 𝑟 (which is what 𝑟∗
represents).
Example:
(𝑎𝑏)∗ = 𝜀 ∪ 𝑎𝑏(𝑎𝑏)∗
Idempotent Law
Identity: 𝑟 ∪ 𝑟 = 𝑟
results in the same regular expression. Since 𝑟 ∪ 𝑟
Where: The union of a regular expression with itself
matches the same set of strings as 𝑟, it can be
simplified to 𝑟.
Example:
𝑎 ∪ 𝑎=𝑎
The expression a ∪ a is the same as just a.
Distributive Law
Identity: 𝑟(𝑠 ∪ 𝑡) = 𝑟𝑠 ∪ 𝑟𝑡
concatenate 𝑟 with the union of 𝑠s and 𝑡, it’s the same
Where: Concatenation distributes over union. If you
as concatenating 𝑟 with each part separately and then
taking their union.
Example:
𝑎(𝑏 ∪ 𝑐) = 𝑎𝑏 ∪ 𝑎𝑐
The expression a(b ∪ c) can be simplified to ab ∪ ac.
Associative Laws
Union: (𝑟 ∪ 𝑠) ∪ 𝑡 = 𝑟 ∪ (𝑠 ∪ 𝑡)
Concatenation: (𝑟𝑠)𝑡 = 𝑟(𝑠𝑡)
Where: Union and concatenation are associative, meaning that
grouping doesn't affect the result. You can change the grouping of
unions or concatenations without changing the meaning of the
regular expression.
Example (Union):(𝑎∪𝑏)∪𝑐 = 𝑎∪(𝑏∪𝑐)
Both expressions match any string that is either a, b, or c.
Example (Concatenation):(𝑎𝑏)𝑐 = 𝑎(𝑏𝑐)
Both expressions match the string abc.
Commutative Law for Union
Identity: 𝑟 ∪ 𝑠 = 𝑠 ∪ 𝑟
Where: The order of union does not matter. Union is
commutative, so swapping the order of regular
expressions in a union does not change the result.
Example:𝑎∪𝑏=𝑏∪𝑎
Both expressions match either the string a or the string
b.
Annihilation for Concatenation with the
Empty Set
Identity: 𝑟∅ = ∅𝑟 = ∅
Where: Concatenating any regular expression 𝑟 with
the empty set results in the empty set, since the empty
set represents no strings, and concatenating with it
yields no strings.
Example:𝑎∅=∅
The expression a∅ is equivalent to ∅.
Absorption Laws
Identity 1: 𝑟 ∪ (𝑟𝑠)=𝑟
Identity 2: 𝑟 ∪ (𝑠𝑟)=𝑟
Where: If a regular expression 𝑟 is already included in
the union with 𝑟𝑠 or 𝑠𝑟, the union simplifies to 𝑟.
Example:
𝑎∪(𝑎𝑏)=𝑎
The expression a ∪ ab simplifies to just a.
Short Quiz: Identify the Identities of the
given Language
1. Language: {ε, a, aa, aaa, aaaa, ...}
2. Language: {ε, a, b, aa, ab, ba, bb, aaa, aab, ...}
3. Language: {ab, aab, aaab, ...}
4. Language: {abd, acd}
5. Language: {ε, 01, 10, 0101, 1010, 0110, 1001, ...}