Understanding Regular Expressions: Operators and Semantics

1. The Building Blocks: Regular Operations on Languages

Before we can define regular expressions, we must first understand the three fundamental operations they use to construct languages. These are operations that take one or two languages (which are sets of strings) and produce a new language.

The following video from MIT OpenCourseWare introduces these three "regular operations."

Let's formalize these definitions. For the following, let $L_1$ and $L_2$ be two languages.

• Union: The union of $L_1$ and $L_2$, written $L_1\cup L_2$, is the set of strings that are in $L_1$, or in $L_2$, or in both. This is the standard set union operation you're familiar with.

  $$L_1\cup L_2=\{w\mid w\in L_1\text{ or }w\in L_2\}$$

• Concatenation: The concatenation of $L_1$ and $L_2$, written $L_1\circ L_2$ or simply $L_1{L}_2$, is the set of strings that can be formed by taking any string from $L_1$ and appending any string from $L_2$ to it.

  $$L_1{L}_2=\{xy\mid x\in L_1\text{ and }y\in L_2\}$$

  For example, if $L_1=\{\text{‘a‘},\text{‘b‘}\}$ and $L_2=\{\text{‘0‘},\text{‘1‘}\}$, then $L_1{L}_2=\{\text{‘a0‘},\text{‘a1‘},\text{‘b0‘},\text{‘b1‘}\}$. Note that concatenation is not commutative; in general, $L_1{L}_2\ne L_2{L}_1$.

• Kleene Star (or Kleene Closure): The Kleene star of a language $L$, written $L^{\ast }$, is the set of all strings formed by concatenating zero or more strings from $L$.

  $$L^{\ast }=\bigcup _{i\ge 0}{L}^i=L^0\cup L^1\cup L^2\cup \dots$$

  Here, $L^0=\{ϵ\}$ (the language containing only the empty string), $L^1=L$, and $L^i=L{L}^{i-1}$ for $i>1$. The inclusion of $L^0$ is crucial: the empty string $ϵ$ is always a member of $L^{\ast }$, regardless of the language $L$.

The Kleene star can be the trickiest to grasp. The image below provides a clear, step-by-step example.

For a concise summary of these operations, you can review the first page of the following lecture notes.

2. Formal Definition of a Regular Expression

Now that we have the operations, we can formally define what a regular expression is. The definition is recursive, much like definitions for data structures or language grammars you've encountered in computer science.

A regular expression is defined as follows:

1. Base Cases (Atomic Expressions):

   • $\varnothing$ is a regular expression.
   • $ϵ$ is a regular expression.
   • $a$ is a regular expression for any symbol $a\in \Sigma$ (where $\Sigma$ is the alphabet).

2. Inductive Steps (Compound Expressions): If $R_1$ and $R_2$ are regular expressions, then the following are also regular expressions:

   • $(R_1\cup R_2)$ (Union)
   • $(R_1\circ R_2)$ (Concatenation)
   • $(R_1^{\ast })$ (Kleene Star)

Each regular expression $R$ describes or generates a language, which we denote as $L(R)$. The semantics, or meaning, of a regular expression is the language it corresponds to.

The "Syntax and Semantics" table in the following resource provides a perfect, formal mapping from the expression (syntax) to the language it represents (semantics).

Notational Conventions

To make regular expressions easier to read and write, we use a few conventions:

• Operator Precedence: The star operator has the highest precedence, followed by concatenation, and then union. This is similar to how multiplication has precedence over addition in arithmetic.
  • For example, $a\cup b\circ c^{\ast }$ is parsed as $a\cup (b\circ (c^{\ast }))$.
• Omitting Concatenation: The concatenation operator $\circ$ is often omitted, just like the multiplication sign in algebra.
  • For example, $R_1\circ R_2$ is usually written as just $R_1{R}_2$. So, $a{b}^{\ast }c\cup d$ means $(a(b^{\ast }c))\cup d$.
• Alternative Union Symbol: In many programming contexts and some textbooks, the union operator $\cup$ is written as | or +. We will primarily use $\cup$.

3. Examples: From Syntax to Semantics

Let's see these definitions in action. The power of regular expressions comes from combining the basic elements to describe complex patterns.

Let $\Sigma =\{0,1\}$.

• The regular expression **$0^{\ast }10^{\ast }$
  ** describes the language of all strings that contain exactly one '1'.

  • $L(0^{\ast }10^{\ast })=L(0^{\ast })L(1)L(0^{\ast })=\{ϵ,0,00,\dots \}\{1\}\{ϵ,0,00,\dots \}$
  • This results in strings like 1, 01, 10, 00100, etc.

• The regular expression **$(0\cup 1{)}^{\ast }00(0\cup 1{)}^{\ast }$
  ** describes the language of all binary strings that contain 00 as a substring.

  • $(0\cup 1{)}^{\ast }$ describes any binary string.
  • So this expression describes: (any string), followed by 00, followed by (any string).

• The regular expression **$(10{)}^{\ast }\cup (01{)}^{\ast }$
  ** describes the language of strings with alternating 0s and 1s, but only those that start and end with the same character (or are empty).

  • $L((10{)}^{\ast })$ gives ε, 10, 1010, ...
  • $L((01{)}^{\ast })$ gives ε, 01, 0101, ...

The following resources provide more excellent examples.

Conclusion

In this lesson, we established the formal foundation of regular expressions. We moved from an informal, practical understanding to a precise, theoretical one.

Key Takeaways:

• Regular expressions are a formal syntax for describing regular languages, built upon three core operations on languages: union, concatenation, and Kleene star.
• The definition is recursive: we start with atomic expressions ($\varnothing$, $ϵ$, and single alphabet symbols) and combine them using the regular operations.
• Every regular expression $R$ corresponds to a specific language $L(R)$.
• Operator precedence (${}^{\ast }$ > $\circ$ > $\cup$) simplifies the notation by reducing the need for parentheses.

Preview of the Next Lesson:
Now that you can define and interpret regular expressions, the next logical step is to practice creating them. In our next lesson, we will focus on constructing regular expressions for languages with specified patterns. This will hone your ability to translate an English description of a language into its corresponding regular expression, a crucial skill for both theory and practice.