Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 19

Simplifying Regular Expressions with Algebraic Laws

Recommended resources

Hello! Welcome back to our study of regular languages.

In our last lesson, we established the profound connection between regular expressions and finite automata through Kleene's Theorem. We saw that algorithms like the state elimination method can convert any DFA into a regular expression, but the resulting expression can often be complex, lengthy, and difficult to read. Just as in programming where you'd refactor complex code to make it simpler and more maintainable, we need a way to simplify these regular expressions.

This lesson introduces the tools for that simplification. We will explore the algebraic laws of regular expressions, a set of formal rules that allow us to manipulate and simplify expressions while preserving the language they define. By the end of this lesson, you will be able to apply these laws to prove the equivalence of two expressions or to reduce a complex regular expression to a simpler, equivalent form.

An Algebra for Regular Expressions

Just as arithmetic has laws like commutativity (x + y = y + x) and distributivity (x * (y + z) = xy + xz), regular expressions have their own set of algebraic laws. Here, the union operator (+ or |) behaves much like addition, and the concatenation operator (. or juxtaposition) behaves like multiplication.

Let's begin by formally introducing these concepts.

Properties of Regular Languages

These lecture notes, titled 'Properties of Regular Languages' from the University of Orléans, provide a structured overview of the algebraic laws. The document draws a useful analogy between the algebra of regular expressions and the algebra of arithmetic.

Please read pages 2 through 7. These pages cover the core algebraic laws, categorized as: Associativity and Commutativity (page 3) Identities and Annihilators (page 4) Distributive Laws (page 5) The Idempotent Law (page 6) Laws Involving Closures (page 7) Focus on understanding the role of each law and the distinction between operators (e.g., union is commutative, but concatenation is not).

The resource you just read provides a formal foundation. To see a more comprehensive list and hear them explained, let's watch a video that enumerates twelve common laws.

Algebraic Laws of Regular Expression || Identity Rules || Theory of Computation || TOC || FLAT

The video 'Algebraic Laws of Regular Expression' by Sudhakar Atchala provides a quick tour of twelve key identities. It's a useful way to see all the rules in one place.

Watch from 00:31 to 06:48. The presenter will walk through the key laws involving the empty set (∅), the empty string (ε), idempotency, closure, and distributivity. Don't worry about memorizing all twelve at once; focus on getting a feel for the different types of rules available.

Summary of Key Algebraic Laws

To summarize and consolidate, here are the most important laws for simplifying regular expressions. Let R, S, and T be regular expressions.

Identities of Regular Expressions
A clear visual summary of several key algebraic laws for regular expressions, similar to those you'll use for simplification.

1. Commutativity & Associativity:

  • R + S = S + R (Union is commutative)
  • (R + S) + T = R + (S + T) (Union is associative)
  • (RS)T = R(ST) (Concatenation is associative)
  • Note: Concatenation is not commutative: RS ≠ SR in general.

2. Identity & Annihilator Laws:

  • R + ∅ = R (Identity for union)
  • Rε = εR = R (Identity for concatenation)
  • R∅ = ∅R = ∅ (Annihilator for concatenation)

3. Idempotent Law:

  • R + R = R (Union is idempotent)

4. Distributive Laws:

  • R(S + T) = RS + RT (Left distribution)
  • (S + T)R = SR + TR (Right distribution)

5. Laws for Kleene Star (*):

  • (R*)* = R*
  • ε* = ε and ∅* = ε
  • R* = ε + R+
  • R* = ε + RR*
  • RR* = R*R = R+

These laws are the tools we'll use to "refactor" our regular expressions.

Applying the Laws: Simplification in Action

Knowing the laws is one thing; applying them strategically is another. The goal is to transform a complex expression into a simpler, equivalent one by repeatedly applying these rules.

Let's start with a clear, step-by-step example from a set of lecture notes.

Lecture 6 – Regular Expressions and Languages - COSE215

These lecture slides from Korea University, 'Lecture 6 – Regular Expressions and Languages', provide a perfect example of simplification where each step is explicitly justified by a law.

Read slide 15, titled 'Simplifying Regular Expressions'. Follow the simplification of ((a∅)∗(b|∅|b∗))∗. Notice how each transformation is annotated with the specific law being used, such as 'Annihilator' or 'Identity'.

The example on the slide shows a powerful technique: chipping away at a complex expression one piece at a time. The process often starts from the inside out, applying rules like the annihilator law (a∅ = ∅) and identity laws (R+∅ = R, εR = R) to remove redundant parts of the expression.

Now, let's watch a video that demonstrates how to approach simplification as a proof, where you show that a complex Left-Hand Side (LHS) expression is equivalent to a simpler Right-Hand Side (RHS) expression.

Simplification of Regular Expressions in TOC || An Example Proof using Algebraic laws ||Identities

This video, 'Simplification of Regular Expressions', continues where the last one left off. It applies the laws to solve two example problems.

Watch the first example, from 01:05 to 06:06. The presenter simplifies a complex expression by first identifying a common term that can be factored out—a strategy similar to factoring in algebra. Then, key identities like ε + R*R = R* and ε + R* = R* are used to simplify the remaining parts.

The key strategies demonstrated here are:

  1. Factoring: Look for common subexpressions that can be factored out using the distributive law in reverse (e.g., RS + RT = R(S+T)).
  2. Applying Identities: Once the expression is in a certain form, look for opportunities to apply identities, especially those involving ε and *, like ε + RR* = R*.

Now it's your turn to apply these laws.

Test your understanding!

Consider the regular expression from the second example in the video LINK: (ε + 1*01*)*
Note: The video shows 1*011*, but we'll use a slightly different expression to make you think from scratch. Let's simplify (ε + (1*01*))*.

How would you simplify this expression? Justify each step with the name of the law you are using.

Hint: The structure is (ε + R)*. Is there a law that simplifies ε + R when R is a starred expression?

Show answer

Let's simplify (ε + (1*01*))*.

Let R = 1*01*. The expression is (ε + R)*.

  1. We know that R* always contains ε. The language for 1*01* contains strings like 0, 101, 110, etc.
  2. The expression ε + R means the union of the language L(R) with the language containing just the empty string, {ε}.
  3. Since R might or might not contain ε (in this case, 1*01* doesn't), the union ε + R is a way to ensure the empty string is included.
  4. Another way to write ε + R is R? if we use extended notation, but sticking to our basic laws, let's think about (ε + R)*.
  5. A key law is that for any regular expression S, (S*)* = S*.
  6. Another law is (S+T)* = (S*T*)*. Let's use this.
    Let S = ε and T = 1*01*.
    Our expression is (S + T)*.
    This is equivalent to (S*T*)*.
  7. S* = ε* = ε.
  8. So we have (ε (1*01*)*)*.
  9. By the identity law for concatenation, εR = R, this simplifies to ((1*01*)*)*.
  10. Finally, using the law (R*)* = R*, we get (1*01*)*.

A more direct approach uses the identity (ε + R)* = R*. Why is this true? L(R*) already contains L(ε). Taking the union with ε doesn't add any new strings to the language L(R*). Therefore, L(ε + R*) = L(R*).
Applying this logic to our problem (ε + 1*01*)*:

  1. Let R = 1*01*. The expression is (ε + R)*.
  2. The language of (ε + R) includes ε and all strings from L(R).
  3. Taking the Kleene star of (ε + R) means concatenating any number of strings from L(ε + R).
  4. Since ε is the identity for concatenation, any sequence of concatenations involving ε and strings from R will just result in a concatenation of strings from R.
  5. Therefore, the set of strings generated by (ε + R)* is identical to the set of strings generated by R*.
  6. So, (ε + 1*01*)* simplifies to (1*01*)*.

Conclusion

In this lesson, we established a formal algebraic system for manipulating regular expressions. By understanding and applying these laws, you can simplify complex expressions, prove equivalences, and gain a deeper insight into the structure of regular languages.

Key Takeaways:

  • Regular expressions have an algebra with laws for union (+), concatenation (.), and Kleene star (*).
  • These laws, such as associativity, distributivity, idempotency, and identity, are analogous to laws in arithmetic and algebra.
  • By applying these laws systematically, we can simplify complex regular expressions into more readable and often more efficient forms.
  • Simplification often involves strategies like factoring out common expressions and applying identities to eliminate redundancy.

Preview of the Next Lesson:
We have now thoroughly covered the three main representations of regular languages: DFAs, NFAs, and regular expressions, as well as the methods for converting between them and simplifying them. In the next lesson, we will put this knowledge to practical use by exploring one of the most important real-world applications of regular expressions: lexical analysis, the first phase of a compiler. Your experience with building software will make this a particularly relevant and interesting application of the theory.