Notebook 8: Regex to Automaton (Kleene)

Interactive notebook on Kleene’s theorem: write a Regex, generate an NFA via Thompson’s construction, and explore state elimination and the R_i,j^k formulas.

Regex to Automaton & Kleene’s Theorem

This notebook walks through Kleene’s Theorem interactively in three steps:

1. Write a regex → the notebook builds the corresponding NFA via Thompson’s construction.
2. Choose states \(i\), \(j\) and frontier \(k\) → the notebook highlights which states are “allowed” as intermediates.
3. Read off \(R_{i,j}^k\) → the regular expression for all words that go from \(q_i\) to \(q_j\) using only \(q_1, \ldots, q_k\) as intermediate stops.

The key recurrence is: \[ R_{i,j}^k = R_{i,j}^{k-1} + R_{i,k}^{k-1}(R_{k,k}^{k-1})^*R_{k,j}^{k-1} \]

1

Write a Regular Expression

Use letters for symbols, + for union, concatenation is implicit, * for Kleene star, () for grouping.

Regex (e.g. (a+b)*a)

2

Explore the NFA (Thompson's Construction)

Each state is numbered. Drag nodes, zoom with the scroll wheel, or use the buttons to re-fit. Colours reflect the current selection below.

scroll to zoom · drag to pan

Normal state Allowed intermediate (≤ k) Accepting state Start i End j

3

Choose i, j and frontier k

i = start state  ·  j = end state  ·  k = highest-numbered state allowed as intermediate (k = 0 means no intermediates, k = n means all).

Frontier k

Start i

End j

reset

Resulting expression R_?,?^?

Recurrence breakdown (how this R was built)

4

Witness words & word test

Short words (length ≤ 4) belonging to the selected R. If the shortest word in R is longer than 4, a hint will suggest it. Below, test any word you like.

Short words in R_?,?^?

✓ In R_?,?^?

✗ Accepted by NFA but blocked by frontier k

Test your own word

Input word (letters of the alphabet only)

What to notice

When k = 0: \(R_{i,j}^0\) contains only \(\varepsilon\) (if \(i = j\)) and the labels of any direct edges from \(q_i\) to \(q_j\). No intermediate stops allowed.

When k increases by 1: the recurrence adds exactly the paths that use the newly unlocked state \(q_k\) as an intermediate. The star \((R_{k,k}^{k-1})^*\) covers paths that loop back through \(q_k\) zero or more times before leaving.

When k = n: \(R_{i,j}^n\) is unrestricted — any path is allowed — and \(R_{q_0,f}^n\) for each accepting state \(f\) gives one of the summands of the final regular expression.