Deterministický konečný automat (DFA) A = (Q,Σ,δ,q0 ,F) sestává z: konečné množiny stavů, zpravidla značíme Q konečné množiny vstupních symbolů, značíme Σ přechodové funkce, zobrazení z Q × Σ → Q, značíme δ, která bude reprezentovaná hranami grafu počátečního stavu q0 ∈ Q, vede do něj šipka ’odnikud’, a množiny koncových (přijímajících) stavů (final states) F ⊆ Q, označených dvojitým kruhem či šipkou ’ven’.