← 🔤 Lexical Analysis
Subtopic 4 of 6

2.4DFA minimisation

Merge states that are indistinguishable. Start with {final} and {non-final} and keep splitting while transitions lead to different groups. Result is unique (Myhill–Nerode).

DFA states5
Minimal states4

Partition refinement (Moore): split states whose transitions go to different groups.

  • Round 0: {A,B,C,D} {E}
  • Round 1: {A,B,C} {D} {E}
  • Round 2: {A,C} {B} {D} {E}

Round 0 splits final vs non-final. Stop when a round changes nothing.

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.