Introduction to Regular Expressions

Welcome back. In our previous lessons, we explored how to define and recognize the class of regular languages using computational machines—Deterministic and Nondeterministic Finite Automata. We established that these two machine models, despite their different mechanics, are equivalent in power.

Today, we shift from a procedural, machine-based perspective to a declarative, descriptive one. We will introduce regular expressions, a powerful and concise algebraic notation for specifying patterns in strings. You've likely encountered them in programming or using command-line tools, but here we will explore their formal, mathematical underpinnings.

This lesson addresses your core interest in the "science" of CS by asking: instead of building a machine to process strings, can we write a formal description of the set of strings we want? You will learn to define regular expressions formally and, more importantly, to master the art of writing expressions for given language descriptions.

1. The Building Blocks: Regular Operations and Expressions

Just as arithmetic has operations like + and × that build expressions from numbers, the theory of regular languages has its own set of operations. These operations, however, apply to languages (i.e., sets of strings) rather than numbers.

The three fundamental regular operations are:

Union: The union of two languages $L_{1}$ and $L_{2}$ contains all strings that are in $L_{1}$ or in $L_{2}$ .
Concatenation: The concatenation of $L_{1}$ and $L_{2}$ contains all strings formed by taking a string from $L_{1}$ and appending a string from $L_{2}$ to it.
Kleene Star (or Closure): The star of a language $L$ contains all strings formed by concatenating zero or more strings from $L$ . The "zero strings" case always produces the empty string, $ϵ$ .

A regular expression is a syntax for building up descriptions of languages using these operations. The following video from MIT OpenCourseWare introduces these operations and then uses them to formally define regular expressions.

1. Introduction, Finite Automata, Regular Expressions

This video introduces the core concepts from a formal, first-principles perspective.

Please watch the following two segments: Regular operations: This part defines and provides examples for the union, concatenation, and star operations. Regular expressions: This segment builds on the operations to give a formal definition of regular expressions, showing how they are constructed from atomic "building blocks."

Formal Definition Recap

As the video explains, a regular expression over an alphabet $Σ$ is defined inductively. This formal structure should align well with your interest in mathematical rigor.

Basis (Atomic Expressions):
1. $a$ for any $a \in Σ$ is a regular expression denoting the language ${a}$ .
2. $ϵ$ is a regular expression denoting the language ${ϵ}$ .
3. $\emptyset$ is a regular expression denoting the empty language ${}$ .
Inductive Step (Compound Expressions):
If $R_{1}$ and $R_{2}$ are regular expressions, then:
1. $(R_{1} \cup R_{2})$ is a regular expression for the language $L (R_{1}) \cup L (R_{2})$ . (Often written as $R_{1} + R_{2}$ or $R_{1} ∣ R_{2}$ ).
2. $(R_{1} R_{2})$ is a regular expression for the language $L (R_{1}) L (R_{2})$ . (The concatenation operator is often implicit).
3. $(R_{1}^{*})$ is a regular expression for the language $(L (R_{1}))^{*}$ .

To avoid excessive parentheses, we use an order of operations similar to arithmetic: Kleene star has the highest precedence, followed by concatenation, and finally union. For example, $a \cup b c^{*}$ is parsed as $(a) \cup (b (c^{*}))$ .

2. The Bigger Picture: Another Way to Be Regular

You've now seen two very different ways to specify a class of languages: by building a finite automaton (a machine) or by writing a regular expression (a description). It is a cornerstone of theoretical computer science that these two formalisms are equivalent in power.

Kleene's Theorem: A language is regular if and only if some regular expression describes it.

We will prove this theorem in the next lesson. For now, it's crucial to understand this equivalence. Anything you can do with a DFA/NFA, you can do with a regular expression, and vice-versa.

The image below provides a great visual summary, connecting the concepts we've discussed: a regular expression, the language (set of strings) it generates, and the finite automaton that accepts that same language.

Caption: This diagram illustrates the connection between a regular expression (`a(a+b)*`), the formal language description it represents (strings starting with 'a'), and the equivalent DFA that recognizes this language.

3. From Description to Expression: A Practical Guide

Defining regular expressions is one thing; writing them is a skill that requires practice. The goal is to translate an informal, English-language description of a pattern into a formal regular expression.

The following video provides a rapid-fire series of examples that demonstrate common patterns and construction techniques. We'll go through several key examples together.

Regular Expression Examples || Theory of Computation || Automata Theory || FLAT || Design a

This video by Sudhakar Atchala is an excellent workout for building regular expressions. He uses '+' for union, which is a common convention.

Watch the following examples. For each one, try to pause and construct the expression yourself before watching the solution. Any combination: Example 1. The expression for any string of a's and b's is (a+b)*. This is a fundamental pattern representing "any string over this alphabet." Starts with/ends with: Watch Example 2 (ends with 00) and Example 3 (starts with 1, ends with 0). The logic is to combine a fixed part with a variable part, often represented by (0+1)*. Positional constraints: Example 7 (third character from the right is a). This demonstrates how to enforce a character at a specific position by defining what comes before and after it. The expression (a+b)*a(a+b)(a+b) perfectly captures this. Constraints on symbol count: At least two b's. The logic here is to place the required symbols (b's) and surround them with "anything" ((a+b)*). Exactly two b's. This is more constrained. We must ensure only a's can appear in the variable parts, using a* instead of (a+b)*. Constraints on length: Even length string (over {0}). The key is to build the string in blocks of two: (00)*. Odd length string (over {1}). This can be seen as an even-length string with one extra character: 1(11)*.

4. Algebraic Properties of Regular Expressions

Given your mathematical background, you might appreciate that regular expressions have a rich algebraic structure. Just like numbers, regular expression operators have properties like associativity and distributivity. Understanding these can help you simplify and reason about expressions.

The lecture slides below provide a concise list of these properties.

[PDF] Regular Expressions - CS 373: Theory of Computation

These slides from the University of Illinois list the key algebraic laws governing regular expressions.

Review the slide titled "Some Regular Expression Identities". You don't need to memorize them, but notice the parallels to standard algebra: Union is commutative and associative: R \cup S = S \cup R. Concatenation is associative but not commutative. Concatenation distributes over union: R(S \cup T) = RS \cup RT. Identities and Annihilators: Note the roles of \emptyset and \epsilon. Idempotence: (R^*)^* = R^*.

These laws are not just theoretical curiosities; they are the basis for algorithms that optimize and manipulate regular expressions in software.

5. Self-Assessment

Now it's your turn to practice. The following image contains a set of problems from a Theory of Computation course. Try your hand at constructing the regular expressions requested in question 1.i.

Caption: A set of practice problems. Focus on question 1.i, which asks you to write regular expressions for several languages.

Let's try 1.i.a: "Set of strings over ${a, b, c}$ containing at least one $a$ and at least one $b$ ". This is a tricky one! A common mistake is to write something like $(a + b + c)^{*} a (a + b + c)^{*} b (a + b + c)^{*}$ . But this forces the a to appear before the b. The language allows ba, bca, etc.

The correct solution must account for both orderings:

((a + b + c)^{*} a (a + b + c)^{*} b (a + b + c)^{*}) \cup ((a + b + c)^{*} b (a + b + c)^{*} a (a + b + c)^{*})

This demonstrates how union is used to handle "either-or" conditions. Try the other parts of the question to test your understanding.

Conclusion

In this lesson, we introduced regular expressions as a formal, algebraic way to describe languages. We have moved from the "how" of computation (machines) to the "what" (descriptions).

Here are the key takeaways:

Formal Definition: Regular expressions are built inductively from atomic elements ( $a, ϵ, \emptyset$ ) using the three regular operations: union ( $\cup$ ), concatenation, and Kleene star ( $^{*}$ ).
Descriptive Power: They provide a concise and powerful way to specify complex string patterns.
Equivalence to Automata: Regular expressions describe exactly the regular languages—the same class of languages recognized by DFAs and NFAs. This is a fundamental result known as Kleene's Theorem.
Practical Construction: Writing a regular expression involves translating a pattern's logic into the syntax of the operations, often by combining fixed parts with variable parts (Σ*).

In our next lesson, we will complete this circle of ideas by proving Kleene's theorem. We will learn the algorithms to convert any regular expression into an equivalent NFA (Thompson's construction) and any DFA into an equivalent regular expression, solidifying the deep connection between these two powerful formalisms.

Recommended resources