Definice: Konečný automat (KA) je pětice:
M = (Q, S, R, s, F), kde
• Q je konečná množina stavů
• S je vstupní abeceda
• R je konečná množina pravidel tvaru: pa ® q,
      kde p, q Î Q, a Î S È {e}
• s Î Q je počáteční stav
• F Í Q je množina koncových stavů
Konečné automaty: Definice
7/29
• Čistě matematicky, R je relace z Q ´ (S È {e}) do Q
• Místo relačního zápisu (pa, q) Î R, zapisujeme: pa ® q Î R
• pa ® q znamená, že při přečtení a M udělá přechod z p do q
• pokud a = e, není ze vstupní pásky přečten symbol
Matematická poznámka k pravidlům: