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: