Regular Expressions — Mathematics Knowledge System

Overview

A regular expression is a compact algebraic notation for describing a set of strings (a 'language'), built from single symbols combined with concatenation, alternation (OR), and repetition (Kleene star). By Kleene's theorem, regular expressions describe exactly the languages recognizable by finite automata — the same computational power, expressed as an equation instead of a machine diagram.

Intuition

Instead of drawing states and transitions, a regular expression writes the pattern directly: (a|b)*abb describes 'any sequence of a's and b's, ending in abb.' Every practical text editor's 'find' feature and every programming language's string-matching library is an implementation of this exact theory.

Formal Definition

Definition

Regular expressions over an alphabet Σ are built recursively:

\emptyset,\ \varepsilon,\ a \in \Sigma \text{ are regular expressions}

Base cases: empty language, empty string, single symbol

R_1 \cup R_2 \ (\text{or } R_1 | R_2), \quad R_1 R_2, \quad R_1^*

Union, concatenation, and Kleene star, if R₁ and R₂ are regular expressions

Notation

Notation	Meaning
$R^*$	Kleene star: zero or more repetitions of R
$R_1 \mid R_2$	Alternation: matches R₁ or R₂
$\varepsilon$	The empty string

Properties

Equivalence to finite automata

\text{A language } L \text{ is regular} \iff L \text{ is described by some regular expression}

Closure under union, concatenation, star

\text{Regular languages are closed under } \cup, \cdot, {}^*

Applications

Used pervasively in text search, input validation (emails, phone numbers), and compiler lexers.

Worked Examples

Any prefix, then a mandatory final 1.
$(0|1)^*1$

Answer: (0|1)*1

Practice Problems

Difficulty 3/10

Write a regular expression for all strings over {a,b} containing at least one 'a'.

Difficulty 5/10

A web form validates that an entry looks like a basic email: some characters, an '@', more characters, a dot, then 2–4 letters. Write a simplified regex and name the real-world task this represents.

Difficulty 4/10

A DevOps engineer greps server logs for lines with an HTTP 5xx error code (500–599). Write a regex that matches a status code beginning with 5 followed by two digits.

Difficulty 5/10

Which task can a (classical) regular expression NOT do?

Match strings ending in '.txt'Match balanced, arbitrarily-nested parenthesesMatch a 5-digit ZIP codeMatch one or more digits

Common Mistakes

Common Mistake

Believing regular expressions can match any pattern, including nested/balanced structures.

Regular expressions cannot match balanced parentheses of arbitrary depth — that requires a context-free grammar, since finite automata have no memory (stack) to count nesting depth.

Quiz

The most common real-world use of regular expressions is:

Encrypting dataInput validation, search/replace, and log parsingSorting numbersRendering graphics

Regular expressions cannot match balanced nested parentheses because:

Parentheses are special charactersThey describe regular languages, which have no unbounded memory to count nesting depthThey are too slowThey only work on letters

Summary

Regular expressions describe languages using symbols, union, concatenation, and Kleene star.
By Kleene's theorem, they have exactly the power of finite automata — the 'regular languages'.
Regular languages are closed under union, concatenation, and star.
They cannot express nested/balanced structures — that needs context-free grammars.

References

WebsiteWikipedia — Regular expression