Subtopic 2 of 6
2.2Regular expression → NFA (Thompson)
Build ε-NFAs for each symbol and combine with union, concatenation and star. Every fragment has exactly one start and one accept state.
NFA states14
Transitions16
ε-transitions11
Start / accept6 / 13
| 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).
Previous year questions: Lexical Analysis (2)
PYQs are grouped by topic, so this is the full set for Lexical Analysis; try the ones that match this subtopic. Open all 2 on the topic page.