Teorie automatů

Teorie automatů je odvětvím diskrétní matematiky , které studuje abstraktní automaty – počítače reprezentované jako matematické modely – a problémy, které mohou řešit.

Teorie automatů nejvíce souvisí s teorií algoritmů : automat transformuje jednotlivé informace v krocích do jednotlivých okamžiků času a generuje výsledek v krocích daného algoritmu .

Existuje algebraická léčba teorie automatů pomocí semiringů , formálních mocninných řad , formálních řad nad stromy, teorie pevných bodů a teorie matic [1] .

Terminologie

Symbol je jakýkoli atomární (to znamená již nedělitelný bez ztráty významu) blok dat, který může mít vliv na stroj. Nejčastěji je symbolem písmeno nějakého formálního jazyka. Například symboly používané v mnoha programovacích jazycích zahrnují běžná jazyková písmena, oddělovače a některé další znaky. Symbolem ale může být například celé klíčové slovo určitého programovacího jazyka (if, for, while atd.), grafický prvek diagramu atd.

Slovo - řetězec znaků vytvořený zřetězením (spojením).
Abeceda - konečná množina různých znaků (mnoho znaků)
Jazyk je množina slov, která lze skládat (generovat) ze znaků dané abecedy. Jazyk může být konečný nebo nekonečný .

Účel formálních automatů

V teorii automatů je toto slovo chápáno jako formální (matematická) konstrukce, která definuje algoritmus, jehož účelem je určit, zda dané slovo patří do vstupního jazyka popsaného daným formálním automatem. Slovo „formální“ zdůrazňuje rozdíl mezi takovým automatem a automatickými obráběcími stroji, automatickými převodovkami a jinými podobnými zařízeními ztělesněnými v kovu. Přídavné jméno „formální“ nebo „matematický“ je pro stručnost v příslušných příručkách často vynecháváno (počínaje názvem teorie – přesněji by bylo „teorie formálních automatů“), když je jasné, o co jde.

Pořadí provozu stroje

Aby splnily svůj účel, jsou všechny (formální) automaty vybaveny vlastností být v nějakém přípustném stavu a přechodovými funkcemi automatu, v nejjednodušším případě (konečné automaty) specifikujícími pouze možnost přechodu z jednoho stavu do druhého při čtení dalšího znaku. ze vstupního řetězce. Po dalším přechodu se čtecí hlava stroje posune o jeden znak (je "čteno"). To se děje, dokud není dosaženo konce čteného slova nebo není nalezena vhodná přechodová funkce.

Množina všech přípustných stavů automatu je konečná a tvoří abecedu stavů automatu. Z celé množiny stavů se rozlišuje podmnožina počátečních stavů automatu (v jednom z nich může začít parsování slova) a podmnožina koncových (neboli konečných ) stavů, ve kterých automat (pokud je slovo čteno) úplně) může dojít k závěru, že analyzované (vstupní) slovo patří strojovému jazyku. Počáteční a konečný stav automatu se mohou prolínat. Pokud automat vstoupí do konečného (neboli konečného) stavu, indikuje to pouze možnost dokončení analýzy, to znamená, že automat může během provozu mnohokrát projít jedním nebo druhým konečným stavem, zatímco čtení slova pokračuje.

Spuštění a zastavení stroje

Začátek činnosti automatu je zcela určen jeho „počáteční konfigurací“, která zahrnuje analyzované slovo a stav, ve kterém se automat nachází. Pokud je automat v některém z počátečních stavů a existuje pro tento stav přechodová funkce a první symbol čitelného řetězce, automat provede odpovídající přechod, posune čtecí hlavu na vstupním slově a (v nejjednodušším případě , konečné automaty) pokračuje ve zkoumání dalšího vstupního symbolu.

Aby bylo možné přijmout (nebo, jak se říká, přiznat) vstupní slovo automatem, musí být splněny dvě podmínky:

Vstupní slovo musí být přečteno celé
Po přečtení slova je automat (nebo se může dostat přes prázdné přechody, pokud jsou u příslušného typu automatů povoleny) do jednoho z koncových stavů. U některých typů automatů může být toto kritérium formulováno poněkud odlišně a v teorii automatů se dokazuje ekvivalence (ekvivalence) takových formulací zastávky.

„Prázdným přechodem“ nebo „průchodem prázdným symbolem“ zde rozumíme přechod z jednoho stavu do druhého, kdy se ze vstupního slova nečte další znak, nebo jinými slovy „čte se prázdný znak“. Označení viz níže.

Všimněte si, že automat musí akceptovat všechna přípustná slova jazyka, který popisuje, a zároveň nesmí akceptovat jediné slovo, které v tomto jazyce není obsaženo.

Pokud do jazyka nepatří vstupní slovo, pak automat také

zastaví se v konečném počtu kroků, aniž by dočetli do konce slova a aniž by měli vhodnou přechodovou funkci pro pokračování ve čtení
přečte celé slovo, ale nebude v jednom z konečných stavů (nebo u některých typů automatů nebude splněno jiné ekvivalentní kritérium)
vstupuje do nekonečného koloběhu změn přípustných stavů, ve kterém však nebudou současně splněna obě kritéria pro přijetí (připuštění) slova.

Hlavní typy automatů

Podle složitosti analyzovaných jazyků

Formální automaty se obvykle dělí podle vlastností jejich přechodových funkcí, které určují míru složitosti jazyka, který popisuje.

Podle klasifikace N. Chomského jsou známy čtyři hlavní typy (podle rozmanitosti, složitosti) formálních jazyků:

K analýze slov z regulárních jazyků slouží formální automaty nejjednoduššího zařízení, tzv. konečné automaty . Jejich přechodová funkce specifikuje pouze změnu stavů a případně posun (čtení) vstupního symbolu.

Chcete-li analyzovat slovo z bezkontextových jazyků, musíte do automatu přidat „nákupní pásku“ nebo „zásobník“, do kterého se při každém přechodu zapíše řetězec na základě odpovídající abecedy obchodu. Takové stroje se nazývají " obchodní stroje ".

Pro kontextově citlivé jazyky byly vyvinuty ještě složitější lineárně ohraničené automaty a pro obecné jazyky Turingův stroj [2] .

Při bližším seznámení s teorií je zřejmé, že čím složitější je zařízení automatu, tím větší jsou jeho rozpoznávací schopnosti, ale zároveň je práce s ním obtížnější a časově náročnější. Proto se kompetentní matematik a softwarový inženýr snaží vybrat ten nejjednodušší typ automatu, který řeší problém rozpoznávání s patřičnou kvalitou.

Všimněte si, že mnoho úkolů vyhledávání informací na World Wide Web je napsáno z hlediska běžných jazyků (tj. s nejpřísnějšími omezeními) a většina používaných univerzálních programovacích jazyků je poměrně úspěšně implementována na základě bezkontextových gramatik (i když s určitými vylepšeními, viz . "atributové gramatiky"). Mezi několik málo a velmi zvláštních výjimek patří programovací jazyk LISP (LISP), vyvinutý na bázi kontextově citlivých jazyků. A Turingův stroj se přes veškerou svou (teoreticky) univerzálnost a sílu ukazuje jako tak složitý a nepohodlný pro použití v aplikacích, že se používá pouze pro teoretickou analýzu.

Podle jednoznačnosti přechodové funkce

Pro stejnou aktuální konfiguraci (stav automatu, čitelný vstupní symbol a případně některé další parametry pro složité typy automatů, například obsah zásobníku v zásobníkovém automatu), přechodové funkce formálního automat může specifikovat jako jeden (určitý, deterministický) přechod, tak a několik různých. Jinými slovy, pro stejnou konfiguraci automatu je obecně možná existence několika přechodových funkcí.

Nejistota (nedeterminismus) automatu může nastat i tehdy, když každá jeho konfigurace odpovídá pouze jedné přechodové funkci, ale jsou povoleny i přechody po „prázdném řetězci“ (prázdný symbol). Je jasné, že nejednoznačnost přechodu zde může nastat ne v jednom, ale ve více hodinových cyklech automatu.

Na tomto základě se také automaty dělí na deterministické (určité) a nedeterministické. Důležitost tohoto rozdělení se vysvětluje také tím, jak vlastnost determinismu ovlivňuje interpretaci tolerance slova automatem.

Pokud tedy máme deterministický automat, pak pokud nejsou splněny výše uvedené podmínky pro připuštění slova, můžeme rovnou říci, že toto slovo do jazyka nepatří. Máme-li nedeterministický automat, pak v takovém případě uděláme tento závěr pouze pro jednu z možných větví parsování slova. Ve skutečnosti si programátor musí nějakým způsobem zapamatovat všechny možné větve při parsování slova a pokud jedna z větví selže, vrátit se na další větev a prozkoumat jinou větev parsování. A teprve po prozkoumání všech možných možností parsování (pokud žádná ze zprostředkujících větví nesplňovala toleranční podmínky) můžeme s jistotou dojít k závěru, že dané slovo do jazyka nepatří.

Je jasné, že sledování a účtování možných výnosů při parsování slova výrazně komplikuje programátorovi práci. Nabízí se tedy otázka, zda je možné automat transformovat tak, aby se z nedeterministického stal deterministický a v řadě případů tedy pro práci s ním pohodlnější. V teorii automatů bylo prokázáno, že to lze vždy provést pro regulární jazyky a jejich odpovídající konečné automaty. A pro ostatní typy jazyků (podle N. Chomského), počínaje bezkontextovými a jejich odpovídajícími automaty, v obecném případě již ne.

Na druhou stranu je třeba poznamenat, že nedeterministické automaty mají obvykle znatelně menší objem, jejich provozní logika je pro člověka srozumitelnější. Všimněte si, že při použití víceprocesorových (vícejádrových) počítačů samotná možnost paralelizace často úzce souvisí s nedeterminismem algoritmu. Program, jehož všechny části musí být provedeny v přesně definovaném pořadí, nelze paralelizovat ... [2] .

Příklady formálních definic pro konečné automaty

Automaty mohou být deterministické nebo nedeterministické .

Deterministický konečný automat (DFA) je posloupnost ( n-tice ) pěti prvků, kde:

(Q,\Sigma,\delta,S_{0},F)

$Q$ je množina stavů automatu
$\Sigma$ - abeceda jazyka, kterému stroj rozumí
$\delta$ je přechodová funkce taková, že $\delta :Q\times \Sigma \rightarrow Q$
$S_{0}\v Q$ - výchozí stav
$F\subseteq Q$ je soubor konečných stavů.

Nedeterministický konečný automat (NFA) je posloupnost (n-tice) pěti prvků, kde:

(Q,\Sigma,\Delta,S,F)

$Q$ je množina stavů automatu
$\Sigma$ - abeceda jazyka, kterému stroj rozumí
$\Delta$ je přechodový vztah, , kde je prázdné slovo. To znamená, že NFA může provést přechod ze stavu q do stavu p , na rozdíl od DFA, přes prázdné slovo (tj. bez čtení dalšího znaku ze vstupu), a také přejít z q do a do jednoho z několik stavů (v DFA je možný přechod z q přes a do ne více než jednoho stavu z Q, odtud jistota (nebo v angličtině determinismus) všech přechodů takového automatu a jeho názvu). ${\displaystyle \Delta =\{<q,a,p>:q,p\in Q,a\in \Sigma \cup \{e\}\))$ $\{E\}$
$S\subseteq Q$ — sada počátečních stavů
$F\subseteq Q$ je soubor konečných stavů.

Slovo Automat přečte konečný řetězec znaků a 1 , a 2 , …., a n , kde a i Σ, které se nazývá vstupní slovo . Množina všech slov se zapisuje jako Σ*.

\v

Přijaté slovo Slovo w Σ* je akceptováno automatem, pokud q n F.

\v

\v

O jazyce L se říká, že je čitelný (akceptovaný) automatem M, pokud se skládá ze slov w podle abecedy tak, že pokud jsou tato slova zapsána do M, po ukončení zpracování se dostane do jednoho z akceptujících stavů F: $\Sigma$

L=\{w\in \Sigma ^{{\star }}|{\hat \delta }(S_{0},w)\in F\}

Automat obvykle přechází ze stavu do stavu pomocí přechodové funkce , přičemž čte jeden znak ze vstupu. Existují automaty, které dokážou přejít do nového stavu bez přečtení znaku. Přechodová funkce bez přečtení znaku se nazývá -jump (epsilon-skok). $\delta$ $\epsilon$

Aplikace

Teorie automatů je základem všech digitálních technologií a softwaru, například počítač je speciálním případem praktické implementace konečného automatu.

Část matematického aparátu teorie automatů se přímo využívá při vývoji lexikálních a syntaktických analyzátorů pro formální jazyky včetně programovacích jazyků , dále při konstrukci kompilátorů a vývoji samotných programovacích jazyků, popisů hardwaru a značek . .

Další důležitou aplikací teorie automatů je matematicky přesné stanovení řešitelnosti a složitosti problémů.

Typické úkoly

Konstrukce a minimalizace automatů - konstrukce abstraktního automatu z dané třídy, který řeší daný problém (akceptuje daný jazyk), případně s následnou minimalizací počtem stavů nebo počtem přechodů.
Syntéza automatů je konstrukce systému daných „elementárních automatů“, ekvivalentních danému automatu. Takový automat se nazývá strukturální . Používá se např. při syntéze číslicových elektrických obvodů na dané elementové bázi.

Viz také

Poznámky

↑ Moderní teorie automatů , 2013 , str. 5.
↑ 1 2 Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků Archivní kopie ze dne 3. ledna 2022 na Wayback Machine - M.: MZ-Press, 2006., 2. vyd. — ISBN 5-94073-094-9

Literatura

Viktor Michajlovič Gluškov . Syntéza číslicových automatů. - M . : Státní nakladatelství fyzikální a matematické literatury, 1962. - S. 476.

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M. : Williams, 2002. - S. 528. - ISBN 0-201-44124-1 .
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků - M.: MZ-Press, 2006, 2. vyd. — ISBN 5-94073-094-9
Kasyanov VN Přednášky o teorii formálních jazyků, automatech a výpočetní složitosti. - Novosibirsk: NGU, 1995. - S. 112.
Moderní teorie automatů. Kaliningrad: Izd-vo BFU im. I. Kant, 2013. 261 s.: ill. ISBN 978-5-9971-0273-9 .

Odkazy

Aplikace teorie automatů

Slovníky a encyklopedie

V bibliografických katalozích
BNF : 119395737 GND : 4003953-5 J9U : 987007541154705171 LCCN : sh85079341 LNB : 000068036 NDL : 00568995 NKC : ph126547