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

Source: https://skills101.in/learn/theory-of-computation/regular-expressions-regular-languages — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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 | `0*10*10*` |

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

```python
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}")
```

```text
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:

![Thompson's construction: a single symbol is one transition; union adds a new start with epsilon moves into both machines and epsilon moves out to a new end; concatenation links the first machine's end to the second's start with epsilon; star adds epsilon loops for zero or more repetitions](https://skills101.in/learn-img/theory-of-computation/thompson.svg)

- **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* | ε* = ε, ∅* = ε |
| R*R* = R* | (R + S)* = (R*S*)* |
| 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.

```python
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))}")
```

```text
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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/regular-expressions-regular-languages