Almost every programmer has used a regular expression at some point, whether to validate an email address in a web form, search for a pattern inside a text editor, or extract specific fields from a log file. What many programmers never realize is that this everyday tool has its roots directly in Theory of Computation, built on the exact same mathematical foundation as the finite automata studied in earlier chapters.
A regular expression is, at its core, just a compact way of writing down a language. Instead of drawing a transition diagram with circles and arrows, a regular expression describes the same set of strings using a short line of symbols and operators. This compactness is precisely what makes regular expressions so convenient in practice, and understanding how they connect back to automata explains why they behave the way they do, including why certain patterns are impossible to express using a regular expression alone.
In this tutorial, you will learn the formal definition of a regular expression, the core operators used to build them, how precedence rules determine how a complex expression should be read, and how regular expressions relate directly to the finite automata studied earlier in this course. Several worked examples are included to connect the abstract rules to patterns you might actually recognize from everyday programming.
A regular expression is a formal notation used to describe a regular language, meaning any language that can also be recognized by some finite automaton, whether deterministic or non-deterministic. Regular expressions are built up from individual symbols of an alphabet using a small set of operators, and every regular expression corresponds to exactly one language, namely the set of all strings that match the pattern it describes.
This relationship works in both directions, and this fact is one of the most important results connecting the last three chapters of this course. Every regular expression can be converted into an equivalent NFA, and by extension into an equivalent DFA using the subset construction method from the previous chapter. Likewise, every finite automaton can be converted back into an equivalent regular expression. Because of this two-way relationship, regular expressions, NFAs, and DFAs are all considered different notations for describing exactly the same class of languages, called regular languages.
Regular expressions over an alphabet Σ are defined recursively, meaning simple regular expressions form the base cases, and more complex regular expressions are built by combining simpler ones using specific operators.
| Base Case | Meaning |
|---|---|
| ∅ | Represents the empty language, a language containing no strings at all. |
| ε | Represents the language containing only the empty string. |
| a, for any symbol a in Σ | Represents the language containing exactly one string, the single symbol a. |
Starting from these base cases, larger regular expressions are constructed using three core operators, each corresponding directly to one of the language operations discussed in an earlier chapter on sets and languages.
| Operator | Notation | Meaning |
|---|---|---|
| Union | R1 + R2, sometimes written R1 | R2 | Matches any string that matches either R1 or R2. |
| Concatenation | R1 R2 | Matches any string formed by a match of R1 immediately followed by a match of R2. |
| Kleene Star | R* | Matches zero or more repetitions of whatever R matches, including the empty string. |
Every regular expression, no matter how complicated it looks, is ultimately built from nothing more than these base cases combined repeatedly using union, concatenation, and Kleene star. This small toolkit is surprisingly expressive, capable of describing everything from fixed keywords to open-ended repeating patterns.
Just like arithmetic expressions follow an order of operations, regular expressions follow a fixed precedence when multiple operators appear together without parentheses. Understanding this precedence is essential for reading a regular expression correctly, since an expression like ab*c can be easily misread if the precedence rules are not clear.
| Precedence | Operator |
|---|---|
| Highest | Kleene star (*) |
| Middle | Concatenation |
| Lowest | Union (+) |
Expression: ab*c Correct reading: a, followed by zero or more b, followed by c Because star binds tighter than concatenation, only the b is repeated, not "ab" as a whole. Matching strings: "ac", "abc", "abbc", "abbbc" Non-matching strings: "abac", "bc"
Expression: a + bc* Correct reading: either "a" alone, or "b" followed by zero or more c Because union has the lowest precedence, it splits the expression into two separate alternatives. Matching strings: "a", "b", "bc", "bcc", "bccc" Non-matching strings: "ab", "ac"
Parentheses can always be used to override the default precedence, exactly as they do in arithmetic. Writing (ab)* instead of ab*, for example, changes the meaning entirely, now repeating the entire two-symbol sequence "ab" as a whole rather than repeating only the b.
Suppose the task is to write a regular expression over the alphabet Σ = { 0, 1 } describing every string that contains at least one 1. Rather than jumping straight to the final answer, it helps to think through the structure of the language first.
Any string containing at least one 1 can be broken into three conceptual parts: an arbitrary sequence of 0s and 1s before the first required 1, the required 1 itself, and another arbitrary sequence of 0s and 1s afterward. Since "an arbitrary sequence of 0s and 1s" is exactly what (0+1)* describes, matching zero or more repetitions of either symbol, the full expression follows naturally.
Regular expression: (0+1)* 1 (0+1)*
String: 0011 Matches as: (0+1)* = "00", then 1, then (0+1)* = "1" Result: Matches String: 000 No way to match the required middle "1" since the string contains no 1 at all. Result: Does not match String: 1 Matches as: (0+1)* = "", then 1, then (0+1)* = "" Result: Matches
This step-by-step way of building a regular expression, breaking the target language into smaller conceptual pieces and combining them with union, concatenation, and Kleene star, is by far the most reliable approach for beginners, far more dependable than trying to guess the final expression all at once.
Consider the language of every string over Σ = { a, b } that starts with an a and ends with a b. Breaking this down: the string must begin with exactly one a, may contain any arbitrary sequence of a and b symbols in the middle, and must end with exactly one b.
Regular expression: a (a+b)* b
String: aab Matches as: a, then (a+b)* = "a", then b Result: Matches String: ab Matches as: a, then (a+b)* = "", then b Result: Matches String: ba Does not start with a. Result: Does not match String: a Does not end with b. Result: Does not match
Notice how the middle portion, (a+b)*, does all the heavy lifting of allowing any combination of symbols in between, while the fixed a at the start and fixed b at the end anchor the required structure of the string.
Every regular expression can be systematically converted into an equivalent NFA using a recursive construction, often taught alongside a method known as Thompson's construction. The basic idea mirrors the recursive definition of regular expressions themselves: build tiny automata for the base cases, a single symbol, the empty string, and the empty language, and then combine these tiny automata together using specific rules whenever union, concatenation, or Kleene star is applied.
| Regular Expression Operator | Corresponding NFA Construction |
|---|---|
| Union (R1 + R2) | A new start state is added with epsilon transitions branching into the start of both R1's and R2's automata. |
| Concatenation (R1 R2) | The accepting state of R1's automaton is connected using an epsilon transition to the start state of R2's automaton. |
| Kleene Star (R*) | Epsilon transitions are added allowing the automaton to skip R entirely, repeat R any number of times, and loop back after each repetition. |
Once this NFA has been constructed, it can be converted into an equivalent DFA using the exact subset construction method covered in the previous chapter. This chain, from regular expression to NFA to DFA, is precisely how many real-world regular expression engines and lexical analyzers are implemented internally, even if the programmer using them never sees any of these intermediate automata directly.
Despite their usefulness, regular expressions are not capable of describing every possible language. Since regular expressions are equivalent in power to finite automata, they inherit exactly the same limitations discussed in the earlier chapter on finite automata, particularly the inability to count or match unbounded, nested structures.
A classic example is the language of balanced parentheses, where every opening parenthesis must eventually be matched by a corresponding closing parenthesis. No regular expression can correctly describe this language for parentheses of arbitrary depth, since doing so would require the ability to count how many opening parentheses have appeared so far, a capability that finite automata, and therefore regular expressions, simply do not have. This exact limitation is what motivates the next major computational model introduced later in this course, the pushdown automaton, which adds a stack capable of counting and matching nested structures.
| Mistake | Correct Understanding |
|---|---|
| Misreading precedence, assuming concatenation binds tighter than Kleene star. | Kleene star always has the highest precedence, applying only to the symbol or group immediately before it. |
| Confusing the empty language ∅ with the empty string ε. | ∅ represents a language with no strings at all, while ε represents a language containing exactly one string, the empty string. |
| Assuming regular expressions can describe any language. | Regular expressions can only describe regular languages, which excludes languages requiring unbounded counting, such as balanced parentheses. |
| Forgetting that Kleene star allows zero repetitions. | R* always matches the empty string as one of its possibilities, in addition to any number of repetitions of R. |
Regular expressions provide a compact, symbolic way of describing exactly the same class of languages recognized by finite automata, built from a small set of base cases and three core operators: union, concatenation, and Kleene star. Understanding their precedence rules and their direct connection to NFAs and DFAs explains both why regular expressions are so convenient for everyday pattern matching, and why they fundamentally cannot describe certain languages that require counting or nested structure.
In this tutorial, you learned the formal definition and operators of regular expressions, worked through several examples building expressions step by step, explored how regular expressions convert into equivalent finite automata, and reviewed where these patterns show up in real software tools. With this foundation, you are ready to move on to regular grammars, another equivalent notation for describing regular languages, this time built using production rules rather than symbolic operators.