Regular Expressions and Regular Languages For students.

A regular expression (regex) is a compact pattern language for describing sets of strings — for example, (a|b)*abb describes every string of a's and b's that ends in abb. A regular language is any set of strings that some regex (equivalently, some finite automaton) can describe. Regexes are the everyday tool; regular languages are the mathematical idea behind them.

This matters because searching, validating, and transforming text is half of practical programming. Email validation, finding phone numbers in documents, syntax highlighting in editors, and log analysis all run on regex. Knowing what regex can and cannot describe — its real limits — saves hours of fighting patterns that were doomed from the start.

Key Concepts

• Literals: ordinary characters match themselves.
• Alternation (|): a|b means "a or b".
• Concatenation: ab means a followed by b.
• Kleene star (*): zero or more repetitions; plus (+): one or more; question mark (?): zero or one.
• Character classes: [0-9] matches any digit, \\d the same, \\w word characters.
• Anchors: ^ start of string, $ end of string.
• Regular language: any language describable by a regex — equivalently, by a DFA/NFA (Kleene's theorem).
• Thompson's construction: the algorithm turning any regex into an equivalent NFA, which is how regex engines compile patterns.

How It Works

1. A regex engine compiles your pattern into an NFA using Thompson's construction — each operator becomes a small NFA fragment wired together — then simulates it against the input text.
2. Matching proceeds left to right: the engine tries to consume input symbols following the pattern's operators, exploring parallel paths when choices like alternation or star appear.
3. A match succeeds if some path consumes the required portion of input and satisfies the anchors.
4. Because regexes compile to finite automata, they use only finite memory — which is also why they fundamentally cannot count unboundedly or match nested structures like balanced parentheses; that needs a stronger machine, a pushdown automaton.

Worked Example

Pattern (a|b)*abb over alphabet {a, b} — strings ending in "abb". Test "babaabb":

1. The (a|b)* part can consume any mix; let it consume "baba" (4 symbols).
2. Remaining input is "abb"; the literal "abb" matches it symbol for symbol.
3. Nothing is left over and the pattern is complete → match; "babaabb" is in the language.

Now test "abba": (a|b)* could consume "a", leaving "bba" — the final literal needs "abb" but sees "bba" → fail at the second symbol. Try other splits: consume "ab", leaving "ba" — too short for "abb". Every split fails → "abba" is rejected. The engine's systematic trying of splits is exactly NFA path exploration in disguise.

Common Misconceptions

• "Regex can parse HTML or nested brackets." It cannot — balanced nesting needs memory of arbitrary depth, beyond finite automata; use a real parser.
• ".* is harmless." Unconstrained greedy stars cause catastrophic backtracking on some inputs, freezing programs — anchor patterns and prefer specific classes.
• "Two different-looking regexes must mean different languages." (a|b)* and (a*b*)* describe the same language; equivalence of regexes is decidable but not obvious.

Real-World Applications

• Input validation in web forms and grep/log searching.
• Syntax highlighting in code editors.
• Data extraction and cleaning pipelines.
• Compiler lexers generated from regex specifications.

Regexes describe regular languages with just literals, alternation, concatenation, and stars, and engines run them as automata. The "abb" trace shows matching is systematic path-finding. Respect their limits — no counting, no nesting — and regex becomes the sharpest text tool you own.