Definice: Nechť M = (Q, S, R, s, F) je DSKA a nechť p, q Î Q, p ¹ q. Stavy p a q jsou rozlišitelné  pokud existuje řetězec w Î S* takový, že:
pw |–* p’ and qw |–* q’, kde p’, q’ Î Q a
((p’ Î F a q’ Ï F) nebo (p’ Ï F a q’ Î F)).
Jinak stavy p a q jsou nerozlišitelné.
Rozlišitelné stavy
Myšlenka: Řetězec w rozlišuje stavy p a q, pokud se DSKA „dostane“ z právě z jedné z konfigurací pw a qw do koncového stavu.
36/44