Regular Expressions

What is a regular expression?

A regular expression (regex) is a compact way to describe a set of strings — a pattern. You use them in search boxes, form validation, programming and the command line.

The three core operations

Every regex is built from single characters using just three operations:

Handy shorthands built from these:

Parentheses group: (ab)* matches “”, “ab”, “abab”, …

From regex to automaton: Thompson’s construction

Kleene’s theorem says regular expressions and finite automata describe exactly the same languages. Thompson’s construction turns any regex into an NFA with ε-moves, recursively:

• a single character a → two states joined by an arrow labelled a,
• AB → connect A’s end to B’s start with ε,
• A|B → a new start with ε-arrows to both, and both ends ε-arrow to a new end,
• A* → ε-arrows that let you skip A or loop back to repeat it.

The 3D model builds exactly this NFA from your regex. S is the start state and A the accept state.

Running it: sets of states

1. Start with the ε-closure of S — all states reachable with ε-arrows alone.
2. For each character, follow every arrow labelled with it, then take the ε-closure again.
3. At the end, the string matches if the accept state is among the active states.

This takes O(n · m) time — linear in the text. Tools like grep, RE2 and Rust’s regex crate use this approach.

Code

import re

print(bool(re.fullmatch(r"(a|b)*abb", "aababb")))   # True
print(bool(re.fullmatch(r"colou?r", "colour")))     # True

# Practical patterns
email = re.compile(r"[\w.+-]+@[\w-]+\.[\w.]+")
print(email.findall("write to [email protected] or [email protected]"))

phone = re.compile(r"\+?91[\s-]?\d{5}[\s-]?\d{5}")   # Indian mobile numbers
print(bool(phone.fullmatch("+91 98765 43210")))

re.fullmatch checks the whole string (like the model); re.search finds the pattern anywhere inside it.

Backtracking and “catastrophic” regexes

Python, Java and JavaScript use backtracking engines, which support extra features (back-references like (\w)\1) but can take exponential time on patterns such as (a+)+b against “aaaaaaaaaaaaaaaaaaaaaa!”. Such bugs have taken real websites down. Keep patterns simple, or use a linear-time engine.

Where are regular expressions used?

Search and replace in editors, input validation (emails, phone numbers, PIN codes), log analysis, compilers’ lexical analysers, data cleaning, and grep/sed on the command line.

Common mistakes

• Forgetting that . matches any character — escape it as \. for a literal dot.
• Using regex for nested structures like HTML or balanced brackets — that needs more than a finite automaton.
• Confusing “match anywhere” with “match the whole string”.