Ji°φ Peterka

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∞.