DFA → regular expression
State elimination: rip out one state at a time, relabelling the paths that went through it.
Hopcroft 2e, §3.2.2
Source · DFA
Result
Nothing built yet — step forward to watch it appear.
Working
| From | To | Reads |
|---|---|---|
| q0 | q1 | 0 |
| q0 | q0 | 1 |
| q1 | q1 | 0 |
| q1 | q2 | 1 |
| q2 | q2 | 0+1 |
| S | q0 | ε |
| q2 | F | ε |
Add a new start S and a new accepting state F, joined to the machine by ε-transitions. Now there is exactly one way in and one way out, whatever the original machine looked like.
The answer appears at the last step. if you would rather read it than watch it.
How to read itHopcroft 2e, §3.2.2
- A fresh start and a fresh accepting state come first, so there is one way in and one way out.
- Removing r turns every p → r → q into a single edge labelled R(p,q) + R(p,r) R(r,r)* R(r,q).
- When only the two new states remain, the label between them is the answer.