Regular Expressions in TOC — Regex to NFA, Closure Properties, Examples

Finite automata describe regular languages as machines; regular expressions describe the same languages as patterns. Kleene's theorem says they are exactly equivalent — and that equivalence is why grep, form validators and lexers are fast.

1. Formal regular expressions

Built from symbols with three operations (plus brackets):

Regex	Language	Example
`a`	{a}
`ε`	{ε}
`∅`	{}
R + S (union, written `\|` in code)	L(R) ∪ L(S)	`a + b` = {a, b}
RS (concatenation)	L(R)L(S)	`ab` = {ab}
R* (Kleene star)	zero or more	`a*` = {ε, a, aa, …}

Precedence: star > concatenation > union. So ab* + c means (a(b*)) + c.

2. Writing regex for common languages (Σ = {0, 1})

Language	Regex
all strings	`(0+1)*`
ends in `01`	`(0+1)*01`
contains `11`	`(0+1)11(0+1)`
starts and ends with the same symbol	`0(0+1)0 + 1(0+1)1 + 0 + 1`
even length	`((0+1)(0+1))*`
no two consecutive 1s	`(0 + 10)*(ε + 1)`
exactly two 1s	`01010*`

Let's verify each against a plain definition using Python's re (where | is union and fullmatch means "the whole string"):

import re
from itertools import product

cases = {
    "ends in 01":         (r"[01]*01",            lambda s: s.endswith("01")),
    "contains 11":        (r"[01]*11[01]*",       lambda s: "11" in s),
    "same first & last":  (r"0[01]*0|1[01]*1|0|1", lambda s: len(s) > 0 and s[0] == s[-1]),
    "even length":        (r"([01][01])*",        lambda s: len(s) % 2 == 0),
    "no 11":              (r"(0|10)*(1)?",        lambda s: "11" not in s),
    "exactly two 1s":     (r"0*10*10*",           lambda s: s.count("1") == 2),
}
strings = ["".join(t) for n in range(11) for t in product("01", repeat=n)]
for name, (rx, ok) in cases.items():
    agree = all(bool(re.fullmatch(rx, s)) == ok(s) for s in strings)
    print(f"{name:18} {rx:22} correct on {len(strings)} strings: {agree}")

ends in 01         [01]*01                correct on 2047 strings: True
contains 11        [01]*11[01]*           correct on 2047 strings: True
same first & last  0[01]*0|1[01]*1|0|1    correct on 2047 strings: True
even length        ([01][01])*            correct on 2047 strings: True
no 11              (0|10)*(1)?            correct on 2047 strings: True
exactly two 1s     0*10*10*               correct on 2047 strings: True

3. Regex → automaton (Thompson's construction)

Every regex can be turned into an ε-NFA by combining small pieces:

symbol a: start —a→ accept
R + S: new start with ε to both, both ε to a new accept
RS: R's accept ε→ S's start
R*: new start/accept; ε to skip, ε loop back for repetition

Then subset construction (lesson 3) gives a DFA, and minimisation (lesson 5) gives the smallest DFA. The reverse direction (DFA → regex) uses state elimination or Arden's theorem (R = Q + RP ⇒ R = QP*).

4. Useful identities

Identity
ε R = R ε = R	∅ R = R ∅ = ∅
R + ∅ = R	R + R = R
(R) = R*	ε* = ε, ∅* = ε
RR = R*	(R + S)* = (RS)*
R(SR)* = (RS)*R

5. Closure properties of regular languages

If L₁ and L₂ are regular, so are:

Operation	Why (machine idea)
union, concatenation, star	Thompson's construction
intersection	product construction (lesson 2)
complement	swap accepting states of a complete DFA
difference L₁ − L₂	L₁ ∩ complement(L₂)
reverse	reverse all arrows, swap start/accept
homomorphism, inverse homomorphism	substitute symbols

Closure properties are a quick proof tool: e.g. if L were regular, then L ∩ a*b* would be regular too — useful for showing languages are not regular (next lesson).

6. Textbook regex vs regex in code

Textbook	Python / Java / JS	Note
`a + b`	`a\|b` or `[ab]`
`(0+1)*`	`[01]*`
—	`a+`	one or more = `aa*`
—	`a?`	optional = `(ε + a)`
—	`\d`, `\w`, `.`	character classes
—	`^`, `$`, `\b`	anchors (or use `fullmatch`)
not regular!	backreferences `(\w+)\1`	beyond regular languages

Practical regex engines add features (backreferences, lookarounds) that go beyond regular languages — and backtracking engines can take exponential time on patterns like (a+)+$ against aaaa…b (ReDoS attacks). Prefer simple patterns, anchors and length limits on user input.

import re

pin = re.compile(r"[1-9][0-9]{5}")                    # Indian PIN code: 6 digits, not starting with 0
mobile = re.compile(r"(\+91)?[6-9][0-9]{9}")
for s in ["302029", "012345", "+919876543210", "5876543210"]:
    print(f"{s:14} pin={bool(pin.fullmatch(s))!s:5} mobile={bool(mobile.fullmatch(s))}")

302029         pin=True  mobile=False
012345         pin=False mobile=False
+919876543210  pin=False mobile=True
5876543210     pin=False mobile=False

Common mistakes

Forgetting precedence: ab* is a(b*), not (ab)*.
Using search/match instead of fullmatch when validating (partial matches slip through).
Expecting regex to match nested or counted-equal structures (aⁿbⁿ, balanced brackets).
Writing ambiguous, backtracking-heavy patterns on untrusted input.

Quick recap

Regex = union (+), concatenation, star; precedence star > concat > union.
Regex ⇔ ε-NFA ⇔ NFA ⇔ DFA (Kleene's theorem; Thompson's construction + subset construction).
Regular languages are closed under union, concatenation, star, intersection, complement, difference, reverse.
Practical regex adds conveniences; backreferences go beyond regular; beware ReDoS.

Regular Expressions and Regular Languages — Regex to Automata, Closure Properties and Practical Regex