Finite automaton

Každý vědní obor dnes používá nějaké vlastní nástroje, pomocí kterých zkoumá předmět svého zájmu, popisuje jeho vlastnosti a chování, modeluje jej apod. Nejinak je tomu i v těch disciplínách, které se zabývají počítači a jejich fungováním, jejich potenciálními i aktuálními možnostmi, principiálními omezeními a dalšími souvisejícími aspekty. Jednou z těchto disciplín je i tzv. teorie automatů a formálních jazyků (Theory of Automata and Formal Languages), které počítačový svět vděčí mj. za veškerou teorii, jež stojí za dnes tak běžnými překladači vyšších programovacích jazyků. Jedním ze specifických nástrojů, který si tato disciplína vytvořila pro své vlastní potřeby, ale který se s výhodou uplatňuje i jinde (například při specifikaci přenosových protokolů, viz minule), je tzv. konečný automat (finite automaton).

V prvním přiblížení si můžeme představit, že konečný automat je abstraktním modelem reálného systému (například stroje), který postupně přijímá od svého okolí jednotlivé vstupy (např. znaky, symboly) a definovaným způsobem na ně reaguje. Zmíněné zobecnění přitom spočívá v tom, že se zcela abstrahuje od jakýchkoli realizačních aspektů a dalších technických detailů, pouze se formálně popíší vstupy, které takovýto konečný automat dostává ze svého bezprostředního okolí, a stejně tak se formálním způsobem popíše způsob reakce konečného automatu na tyto vnější vstupy.

Důležitou charakteristikou konečného automatu přitom je, že se snaží modelovat takové systémy, jejichž reakce v daném okamžiku závisí i na historii, resp. na vstupech v dřívějších časových okamžicích. Konečný automat si svou historii "pamatuje" díky tomu, že je vybaven určitým (a to konečným) počtem diskrétních stavů a v každém okamžiku se nachází právě v jednom z nich. Jeho reakce na vnější vstupy je pak definována nejen v závislosti na hodnotě samotného vstupu, ale i na stavu, ve kterém se právě nachází (čímž je dána závislost jeho chování na historii). Konkrétní "činnost" konečného automatu pak probíhá v postupných krocích, přičemž v každém z nich podle aktuálního stavu a podle momentální hodnoty svého vstupu přechází do nového stavu.

Konečným automatem v užším slova smyslu se přitom rozumí právě naznačený abstraktní automat, který nemá žádné výstupy, na počátku se nachází v určitém počátečním stavu a vnějšímu světu pouze signalizuje, zda se v reakci na zadanou posloupnost svých vstupů dostal do určitého konkrétního stavu (chápaného jako koncový), nebo nikoli. Takovýto konečný automat se v teorii automatů a formálních jazyků používá zejména pro potřeby analýzy nejrůznějších formálních jazyků a pro zkoumání a dokazování jejich vlastností.

Chceme-li použít konečný automat například jako prostředek pro popis přenosového protokolu (či pro popis řadiče procesoru nebo pro mnoho podobných účelů), musíme jej nejprve vybavit také určitými výstupy, kterými zpětně působí na své okolí (a které generuje v závislosti na stavu, ve kterém se právě nachází, s uvážením svých momentálních vstupů). Jakmile toto uděláme, z konečného automatu se stává tzv. sekvenční stroj (sequential machine), který však mnohé odborné prameny označují stále ještě jako "konečný automat".

Konečný automat (resp. sekvenční stroj), tak jak jsme si jej právě popsali, je dosti silným prostředkem - postačuje například pro formální popis většiny přenosových protokolů používaných v počítačových sítích. Je ovšem jen jedním z mnoha nástrojů, které si vytvořily teoreticky orientované vědy o počítačích, a není zdaleka prostředkem nejsilnějším. Existují totiž i takové "činnosti" (výpočty, algoritmy), které pomocí konečného automatu namodelovat nelze. Na vině je právě omezení dané konečným počtem stavů automatu - ten je díky tomu schopen si pamatovat například jen konečný počet mezivýsledků (resp. konečný počet kroků ze své "historie"). Konečný automat například nelze použít pro namodelování tak banálního výpočtu, jakým je násobení dvou libovolně velkých čísel - při určité velikosti obou činitelů by si již nedokázal zapamatovat potřebné mezivýsledky v tom počtu stavů, které má k dispozici.

Pokud bychom místo konečného automatu potřebovali použít nějaký "silnější" (resp. univerzálnější) model, museli bychom sáhnout jinam. Ale o tom zase až příště.