section_heading: Odlučivanje regularnosti jezika
paragraph_text: Ako je L neki podskup skupa &Sigma;*, može se definirati relacija ekvivalencije ~ nad &Sigma;* na sljedeći način: u ~ v je definirana na način Jezik L je regularan ako i samo ako broj klasa ekvivalencije relacije ~ je konačan. Ako je to istina, tada je taj broj jednak broju stanja minimalnog konačnog automata koji prihvaća L.