XHTML 1.0 Valid
CSS valid

Teorie - Konečný automat

Úvod|Deterministický KA|Reprezentace|Nedeterministický KA|Normovaný tvar|Minimalizace

Úvod do problematiky

Tato kapitola má za úkol představit teoretický výpočetní model nazývaný konečný automat, s nímž se každý z nás již jistě setkal, i když to není na první pohled zcela patrné. Ve skutečnosti je tento model použit při řízení činnosti automatu na kávu, automaticky otvíraných dveří nebo světelné křižovatky, což jsou pouze ukázkové příklady využití tohoto matematického nástroje. Konečný automat (zkráceně KA) je abstraktní model, který lze využít pro modelování systémů, u nichž lze stanovit konečný počet stavů
a vstupních podnětů. Aktuální stav takovéhoto systému se mění pouze na základě vnějšího podnětu, přičemž platí, že pro daný stav a daný podnět je určeno, do kterého stavu systém přejde. Je vhodné dodat, že KA pracuje v diskrétním čase.

Konečné automaty je možné rozdělit do několika skupin podle zvoleného kritéria. Takto lze KA dělit na deterministické a nedeterministické, další členění může být na KA bez výstupu nebo KA s výstupem. Předmětem zájmu v této práci jsou KA bez výstupu (o KA s výstupem se pojednává např. v [5]). Nejprve bude uvedena definice a popis deterministického KA, u něhož je přechod z aktuálního stavu na základě vstupního symbolu určen jednoznačně. Poté bude uveden i popis nedeterministického KA, pro který předchozí tvrzení neplatí.

Mezi další typy abstraktních matematických modelů používaných v teoretické informatice patří například zásobníkový automat, klasifikační automat nebo Turingův stroj. Zásobníkový automat lze například využít pro zjištění, zda je program zapsaný v nějakém programovacím jazyce validní či ne. Turingův stroj se používá pro určení složitosti algoritmů a při rozhodování, zda je určitý problém automaticky řešitelný. Více se o těchto typech automatů uvádí v [1] nebo [2].

Následující část kapitoly