Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour chaque étiquette possible et si, de plus, il a un seul état initial.
S'il a exactement une transition par étiquette, on parle alors d'automate déterministe complet.
Un automate est déterministe si et seulement si les deux conditions suivantes sont vérifiées : 1.
L'automate possède un et un seul état initial ; 2.
Pour chaque état q et pour chaque lettre α, il existe au plus une transition issue de q d'étiquette α.
Proposition : Un automate déterministe complet est minimal si et seulement si pour tout couple d'états (p,q) il existe un mot qui sépare p et q.
Conséquence : Le résultat précédent donne un moyen de montrer qu'un automate est minimal.
Il suffit d'exhiber pour chaque couple d'état (p,q) un mot qui les sépare.