Konečné automaty a formální jazyky - vypracované otázky

Konečný automat (KA) je abstraktní (virtuální) systém s konečným počtem stavů, na jehož vstup přicházejí symboly vstupní abecedy a KA na jejich příchod reaguje přechodem do následujícího stavu. KA pracuje v diskrétním čase. KA je možno například považovat za abstraktní obraz konkrétního systému, který nahlásí „poruchový“ stav v případě, že sleduje sekvenci symbolů na svém vstupu a ocitne se v tzv. koncovém stavu nebo automat rozpoznává řetězce patřící do nějakého formálního jazyka.

Konečné automaty lze dělit podle různých hledisek.

konečné automaty bez výstupu
konečné automaty s výstupem

konečné automaty deterministické
konečné automaty nedeterministické

Dále se setkáme s
klasifikačním automatem,
niciálním automatem
zásobníkovým automatem

Existuje tedy několik typů konečných automatů. V následujících studijních článcích se s definicemi těchto automatů seznámíte. Konečný automat se může nacházet, jak již bylo řečeno, v konečném počtu stavů. Konečný automat zpracovává konečný počet vstupních symbolů.

Některé automaty nemají výstup, některé výstup mají a pak na tento výstup vydávají výstupní symboly. Hovoříme pak o automatech bez výstupu nebo s výstupem. My se nejprve zaměříme na konečné automaty bez výstupu.

Předpokládáme, že data (vstupní symboly) přicházejí na vstup automatu v diskrétních časových intervalech.

Na automat pohlížíme jako na matematickou strukturu - diskrétní abstraktní (virtuální) dynamický systém, který je definován v následujícím studijním článku.