Notebook 7: Kleene State Elimination

Interactive notebook on Kleene’s theorem and state elimination: convert any DFA to an equivalent regular expression step by step. From the Verification and Validation Techniques course at UniUD.

Kleene’s Theorem: DFA to Regular Expression

This notebook focuses on the state-elimination half of Kleene’s theorem. For a DFA with numbered states \(q_1,\ldots,q_n\), the construction defines \(R_{i,j}^k\) as the set of words that take the automaton from \(q_i\) to \(q_j\) while using only \(q_1,\ldots,q_k\) as intermediate states.

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}. ]

Read it as: either avoid the newly allowed state \(q_k\), or enter \(q_k\), loop around it any finite number of times, and then exit.

Running DFA Even number of a's Contains at least one a

Allowed frontier k

Start i

End j

DFA

Selected R language

Short witness words

Words of length at most 4 that belong to the selected \(R_{i,j}^k\).

Test one word

Input word over {a,b}

What To Notice

The parameter \(k\) does not count how many states the run may visit. It sets which state names may occur in the middle of the run. When \(k\) increases by one, the recurrence adds exactly the words whose path uses the newly unlocked state \(q_k\) as an intermediate stop.

The star appears because once a run reaches \(q_k\), it may return to \(q_k\) zero, one, two, or any finite number of times before leaving.