Theorem 4.2

Theorem 4.2 (Myhill–Nerode theorem, residual form). For a language $L\subseteq\Sigma^*$, the following are equivalent:

1. $L$ is recognized by a finite DFA;

2. $L$ has finitely many left residuals;

3. the relation $\equiv_L$ has finite index.

When these conditions hold, the residual automaton is the unique minimal reachable DFA up to isomorphism.