2.2Regex ⇄ finite automaton
The idea
Regex, NFA and DFA are three descriptions of the same languages, and you can convert between them.
Think of it like this: Three languages for the same recipe: a sentence, a flowchart, and a table.
Why it exists
Conversions let you pick the easiest model for a problem.
How it works
- Regex → ε-NFA: Thompson's construction (every symbol, union or star adds a few states).
- ε-NFA → DFA: subset construction.
- DFA → regex: eliminate states one by one, or solve with Arden's rule R = Q + RP ⇒ R = QP*.
- Minimise the DFA to get the smallest machine.
Worked example: (a + b)*abb
Thompson builds 14 states; subset construction gives 5 DFA states; minimisation leaves 4.
Now play with it
- →Type a regex in the lab, then look at the NFA, DFA and minimal DFA tabs.
- →Run strings on the DFA and watch the state path.
| from | on | to |
|---|---|---|
| 0 | a | 1 |
| 2 | b | 3 |
| 4 | ε | 0 |
| 4 | ε | 2 |
| 1 | ε | 5 |
| 3 | ε | 5 |
| 6 | ε | 4 |
| 6 | ε | 7 |
| 5 | ε | 4 |
| 5 | ε | 7 |
| 8 | a | 9 |
| 7 | ε | 8 |
| 10 | b | 11 |
| 9 | ε | 10 |
| 12 | b | 13 |
| 11 | ε | 12 |
Thompson: each symbol makes 2 states; each | or * adds 2 more; concatenation adds none. So states ≤ 2 × (symbols + operators).
Check yourself
Arden's theorem says that if R = Q + RP and ε ∉ P then R equals
Exam notes (the dense version)
Regex → ε-NFA by Thompson's construction (≤ 2 states per symbol/operator). DFA → regex by state elimination, or by Arden's theorem: if R = Q + RP and ε ∉ P, then R = QP*. All three formalisms describe exactly the regular languages.
Previous year questions: Regular Expressions & Regular Languages (14)
PYQs are grouped by topic, so this is the full set for Regular Expressions & Regular Languages; try the ones that match this subtopic. Open all 14 on the topic page.