konečný automat
konečný automat — inform. automat, ktorý okrem pamäte pre stav nie je vybavený žiadnou ďalšou pamäťou. Dokáže rozpoznávať a prekladať regulárne jazyky. Rozlišuje sa viacero typov konečných automatov.
Deterministický konečný automat (angl. deterministic finite automaton) je rozpoznávací automat (akceptor, → automat) definovaný ako pätica \((\Sigma, Q, \delta, q_0, F)\), kde \(\Sigma\) je konečná vstupná abeceda, \(Q\) konečná množina stavov, \(\delta\) prechodová funkcia, \(q_0\in Q\) začiatočný stav a \(F \subseteq Q\) množina akceptačných (koncových) stavov automatu. Automat znak po znaku načítava vstupné slovo (→ slovo nad abecedou), ktoré pozostáva zo symbolov vstupnej abecedy \(\Sigma\). Jeho stav sa počas načítavania znakov mení na základe načítaného znaku, aktuálneho stavu a prechodovej funkcie. Jeho prechodová funkcia \(\delta\) je jednoznačná a je definovaná ako zobrazenie \(\delta:\Sigma \times Q\rightarrow Q\) (→ deterministický automat). Automat slovo akceptuje, ak sa po načítaní všetkých znakov slova nachádza v niektorom z akceptačných stavov.
Nedeterministický konečný automat (angl. nondeterministic finite automaton) je definovaný rovnako ako deterministický konečný automat, líši sa len typom prechodovej funkcie \(\delta\), ktorá je nejednoznačná a je definovaná ako binárna relácia \(\delta: \Sigma \times Q \rightarrow {\cal P}(Q)\) (→ nedeterministický automat). Schopnosť rozpoznávať jazyky, teda ich výpočtová sila, je pri obidvoch automatoch rovnaká.
Existuje viacero ďalších variantov automatov, napr. dvojsmerný deterministický konečný automat a dvojsmerný nedeterministický konečný automat, ktoré sa pri načítaní vstupu dokážu vrátiť a opakovane načítať znaky vstupného slova, alebo nedeterministický konečný automat s pružnou hlavou, ktorý dokáže zo vstupu načítať viac znakov naraz. Výpočtová sila týchto variantov je rovnaká ako v prípade deterministického konečného automatu.
Mealyho automat a Moorov automat sú deterministické konečné prekladové automaty (transduktory, → automat), ktoré pri načítavaní znakov vstupného slova na svoj výstup zapisujú výstupný znak. Sú definované šesticou \((\Sigma, Q, \delta, q_0, O, r)\), kde symboly \(\Sigma\) , \(Q\) , \(\delta\) , \(q_0\) majú rovnaký význam ako pri deterministickom konečnom automate, \(O\) je výstupná abeceda a \(r\) výstupná funkcia. Pri Mealyho automate je výstupná funkcia \(r\) definovaná ako zobrazenie \(r : \Sigma \times Q \rightarrow O\), čiže výstupný znak je určený na základe aktuálneho stavu automatu a načítaného znaku. Pri Moorovom automate je výstupná funkcia definovaná ako zobrazenie \(r:Q \rightarrow O\), čiže výstupný znak je určený len na základe stavu automatu. Ak je dĺžka vstupného slova \(n\), Mealyho automat zapíše na výstup \(n\) znakov, Moorov automat \(n + 1\) znakov (jeden pre každý vstupný znak a jeden znak pre začiatočný stav \(q_0\)).
Konečné automaty sa používajú na modelovanie procesov, pri ktorých nie je podstatné, čo sa dialo (t. j. v ktorom stave boli) v minulosti. Príkladom je riadiaci systém výťahu, ktorého stav zaznamenáva, na ktorom poschodí sa výťah nachádza a či sa pohybuje nahor alebo nadol. Vstupnými symbolmi sú stlačenia tlačidiel v kabíne alebo vonku. Na ich základe a na základe stavu sa výťah buď rozbehne niektorým smerom, alebo zastaví na niektorom poschodí. Inými príkladmi použitia konečných automatov sú analýza a spracovanie textu pomocou regulárnych výrazov a lexikálna analýza zdrojového kódu počítačového programu.