Fundamental Operations

1. Union (Alternation)

Definition: $r_1 + r_2$ matches strings in $L(r_1)$ or $L(r_2)$

Properties:

• Commutative: $r_1 + r_2 = r_2 + r_1$
• Associative: $(r_1 + r_2) + r_3 = r_1 + (r_2 + r_3)$
• Identity: $r + \emptyset = r$
• Idempotent: $r + r = r$

2. Concatenation

Definition: $r_1 \cdot r_2$ matches strings formed by concatenating a string from $L(r_1)$ with a string from $L(r_2)$

Properties:

• Associative: $(r_1 \cdot r_2) \cdot r_3 = r_1 \cdot (r_2 \cdot r_3)$
• Identity: $r \cdot \epsilon = \epsilon \cdot r = r$
• Annihilator: $r \cdot \emptyset = \emptyset \cdot r = \emptyset$

Warning

Concatenation is not commutative: $a \cdot b \neq b \cdot a$

3. Kleene Star

Definition: $r^*$ matches zero or more concatenations of strings from $L(r)$

Properties:

• Basic: $\emptyset^* = \epsilon^* = \epsilon$
• Iteration: $(r^*)^* = r^*$
• Closure: $\epsilon + r \cdot r^* = r^*$
• Fixed Point: $r^* = \epsilon + r \cdot r^*$

Distributive Laws

Left Distributive

Concatenation over Union: $r \cdot (s + t) = r \cdot s + r \cdot t$

Example: $a \cdot (b + c) = a \cdot b + a \cdot c$

Right Distributive

Union over Concatenation: $(r + s) \cdot t = r \cdot t + s \cdot t$

Example: $(a + b) \cdot c = a \cdot c + b \cdot c`

Tips

These distributive laws allow us to expand and factor regular expressions, similar to algebraic expressions.

Advanced Properties

Absorption Laws

1. Union with Kleene Star: $r + r^* = r^*$
2. Concatenation with Star: $\epsilon + r \cdot r^* = r^*$

Annihilator Properties

• $\emptyset^* = \epsilon$
• $r + \emptyset = r$
• $r \cdot \emptyset = \emptyset$

Proof of $\emptyset^* = \epsilon$

By definition, $r^* = \epsilon + r \cdot r^*$. Let $r = \emptyset$:

• $\emptyset^* = \epsilon + \emptyset \cdot \emptyset^*$
• $\emptyset \cdot \emptyset^* = \emptyset$ (annihilator property)
• Therefore, $\emptyset^* = \epsilon + \emptyset = \epsilon$

Simplification Rules

Basic Simplifications

Original	Simplified	Reason
$r + r$	$r$	Idempotent
$r + \emptyset$	$r$	Identity
$r \cdot \epsilon$	$r$	Identity
$r \cdot \emptyset$	$\emptyset$	Annihilator
$\emptyset^*$	$\epsilon$	Basic property
$\epsilon^*$	$\epsilon$	Basic property

Complex Simplifications

1. Nested Stars: $(r^*)^* = r^*$
2. Empty Concatenation: $\epsilon + r \cdot r^* = r^*$
3. Distributive Expansion: $r \cdot (s + t) = r \cdot s + r \cdot t$

Equivalence and Proofs

Proving Equivalence

To prove $r_1 = r_2$, show that $L(r_1) = L(r_2)$ by demonstrating:

1. Every string in $L(r_1)$ is in $L(r_2)$
2. Every string in $L(r_2)$ is in $L(r_1)$

Example Proof

Theorem: $r^* = \epsilon + r \cdot r^*$

Proof:

• Let $w \in L(r^*)$. Then $w$ can be written as $w_1 w_2 ... w_n$ where each $w_i \in L(r)$ and $n \geq 0$.

  • If $n = 0$, then $w = \epsilon \in \epsilon + r \cdot r^*$
  • If $n \geq 1$, then $w = r_1 \cdot (r_2 ... r_n)$ where $r_1 \in L(r)$ and $r_2 ... r_n \in L(r^*)$

• Therefore $w \in L(\epsilon + r \cdot r^*)$

• Conversely, if $w \in L(\epsilon + r \cdot r^*)$:

  • If $w = \epsilon$, then $w \in L(r^*)$ since $\epsilon^* = \epsilon$
  • If $w \in L(r \cdot r^*)$, then $w = xy$ where $x \in L(r)$ and $y \in L(r^*)$, so $w \in L(r^*)$

Thus $L(r^*) = L(\epsilon + r \cdot r^*)$, so $r^* = \epsilon + r \cdot r^*$.

Algebraic Manipulation

Strategy for Simplification

1. Apply basic identities (idempotent, identity, annihilator)
2. Use distributive laws to expand or factor
3. Apply absorption laws to eliminate redundancy
4. Simplify nested operations (stars, concatenations)

Example Simplification

Original: $(a + b)^* \cdot a \cdot (a + b)^*$

Simplification Steps:

1. Notice this matches any string containing at least one 'a'
2. Equivalent to $(a + b)^+ \cdot a \cdot (a + b)^*$ (at least one 'a' somewhere)
3. Further equivalent to $(a + b)^* \cdot a \cdot (a + b)^*$ (no simpler form)

Common Pitfalls

Incorrect Simplifications

• Not commutative: $a \cdot b \neq b \cdot a$
• Not distributive in reverse: $r + s \cdot t \neq (r + s) \cdot (r + t)$
• Star doesn't distribute: $(r + s)^* \neq r^* + s^*$

Order of Operations

Remember precedence: Kleene Star > Concatenation > Union

Without parentheses: $a + b \cdot c^* = a + (b \cdot (c^*))$

Applications in Compiler Design

Regular Expression Optimization

Understanding algebraic properties allows compilers to:

1. Optimize pattern matching by simplifying regular expressions
2. Generate more efficient DFAs from simplified expressions
3. Avoid redundant computations through algebraic manipulation

Lexical Analysis

In lexical analysis, regular expressions describe tokens:

• Identifiers: $[a-zA-Z][a-zA-Z0-9]^*$
• Numbers: $(0 + 1 + 2 + ... + 9)^+$
• Whitespace: $( + \t + \n)^*$

These can be simplified using algebraic properties before DFA construction.

Summary

The algebraic properties of regular expressions provide a powerful framework for manipulation and simplification. By understanding:

• Fundamental operations and their properties
• Distributive laws and their applications
• Simplification rules and strategies
• Common pitfalls to avoid

We can work effectively with regular expressions in both theoretical analysis and practical implementations. This algebraic structure is the foundation for many applications in computer science, particularly in compiler design and text processing.

Problem-Solving Skills: Simplification Toolkit

1. Normalize forms

   • Push stars inward only when safe; avoid expanding (r+s)^* unless necessary.

2. Remove redundancies

   • Use idempotence r + r = r, absorption r + r^* = r^*.

3. Factor common parts

   • Left/right distributivity to reduce alternation width.

4. Substitute identities

   • r·ε = r, ∅^* = ε, ε + r·r^* = r^*.

5. Sanity-check languages

   • Compare example sets before/after simplification.

Worked Simplifications

Example A:active

Original: (a + ab)^*

Simplify: a(a + b)^*

Reason: Factor a: (a(ε + b))^* is not equal to a(a + b)^* globally, but language-wise we note each block starts with a and is followed by any number of a or b due to repetition. More precise equivalent: (a(ε + b))^* = (a + ab)^*. Use automata check before aggressive rewriting.

Example B

Original: (r + s)·r^*

Simplify idea: r^* absorbs left r but not s:

(r + s)·r^* = r·r^* + s·r^* = r^+ + s·r^*

Example C

Original: r·(s + t)·r^* + r·s·r^*

Simplify: Factor r·s·r^*:

r·(s + t)·r^* + r·s·r^* = r·(s + t + s)·r^* = r·(s + t)·r^*

Proof Patterns

Using language containment

To prove r1 = r2, show both containments by structural induction on strings, or build DFAs and use equivalence testing.

Common Transform Templates

• Remove dead branches: ∅ + r = r, r·∅ = ∅
• Collapse nesting: (r^*)^* = r^*
• Replace plus: r^+ = r·r^*

Tips

When in doubt, convert to a small NFA and minimize the equivalent DFA to validate an algebraic step.

Changelog

8/11/25, 2:48 AM

View All Changelog

• c3bc2-feat: add basic Algebraic Propertieson 8/11/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)