Teorie automatů

Teorie automatů (anglicky automata theory) je studium abstraktních strojů a automatů, včetně výpočetních problémů, které mohou být pomocí nich řešené. Jedná se o obor teoretické informatiky, která patří do diskrétní matematiky (předmět studia matematiky i matematické informatiky). Slovo automaty pochází z řeckého slova αὐτόματα, které znamená „samočinný“.

Obrázek vpravo znázorňuje konečný automat, který patří k dobře známému typu automatů. Tento automat sestává ze stavů (reprezentovaných na obrázku kružnicemi) a přechodů (reprezentovaných šipkami). Když automat načte symbol ze vstupu, provede přechod (nebo skok) do jiného stavu, podle své přechodové funkce, která má jako parametry aktuální stav a načtený symbol.

Teorie automatů má těsnou souvislost s teorií formálních jazyků. Automat je konečnou reprezentací formálního jazyka, který může obsahovat nekonečný počet slov. Automaty jsou často klasifikovány třídou formálních jazyků, kterou mohou rozpoznat.

Automaty hrají hlavní roli v teorii algoritmů, při konstrukci překladačů, v umělé inteligenci, syntaktické analýze a formální verifikaci.

Automaty

Následující popis jednoho typu automatu vysvětluje koncepty používané v teorii automatů.

Neformální popis

Automat si lze představit jako zařízení, které provádí postupně kroky na určité posloupnosti vstupních symbolů. Při každém kroku načte automat jeden vstupní symbol, který patří do množiny symbolů nebo písmen, která se nazývá abeceda. V libovolném časovém okamžiku tvoří symboly dosud načtené automatem konečnou posloupnost nazývanou slovo. Automat má konečnou množinu stavů. V každém kroku, který automat provádí, je v jednom ze těchto stavů. V každém časovém kroku, automat načte jeden symbol, přejde do nového stavu, který je určen funkcí se dvěma parametry: aktuální stav a načtený symbol. Tato funkce se nazývá přechodová funkce. Automat čte symboly vstupního slova jeden po druhém a přechází ze stavu do stavu podle přechodové funkce, dokud není slovo úplně přečteno. Jakmile je načteno celé vstupní slovo, zjistíme, zda je automat v koncovém stavu. Pokud ano, automat vstupní slovo přijal, jinak jej zamítl. Množina všech slova přijímaných automatem se nazývá jazyk rozpoznávaný automatem.

Krátce, automat je matematický objekt, který načítá slovo ze vstupu a rozhoduje, zda jej přijme nebo odmítne. Protože všechny výpočetní problémy jsou převeditelné na otázku přijetí nebo odmítnutí slova (všechny instance problémů mohou být reprezentovány řetězci symbolů konečné délky), hraje teorie automatů klíčovou roli v teorie algoritmů.

Formální definice

Automat

Deterministický konečný automat (anglicky Finite State Automaton,´FSA) je reprezentován formálně pěticí (Q,Σ,δ,q₀,F), kde:

Q je konečná množina stavů (někdy nazývaná vnitřní abeceda).
Σ je konečná množina symbolů, nazývaná vnější abeceda automatu.
δ je přechodová funkce (anglicky transition function), tj. δ: Q × Σ → Q.
q₀ je počáteční stav, tj. stav automatu před načítáním vstupního slova, kde q₀∈ Q.
F je sada stavů Q (tj. F⊆Q) nazývaný koncové stavy (anglicky accept states).

Vstupní slovo: Automat čte konečný řetězec symbolů a₁,a₂,....,a_n , kde a_i ∈ Σ, který se nazývá vstupní slovo. Množina všech slova se označuje Σ*.
Výpočet: Posloupnost stavů q₀,q₁,q₂,...., q_n, kde q_i ∈ Q tak, že q₀ je počáteční stav a q_i = δ(q_i-1,a_i) pro 0 < i ≤ n, je výpočet automat na vstupní slovo w =a₁,a₂,....,a_n ∈ Σ*. Jinými slovy, automat je na začátku ve stavu q₀ a postupně načítá symboly vstupního slova. Po načtení symbolu a_i přejde do stavu q_i = δ(q_i-1,a_i). q_n se nazývá výsledný stav výpočtu.

Přijetí slova: Slovo w ∈ Σ* je přijaté automatem, jestliže q_n ∈ F.

Přijímaný jazyk: Automat může rozpoznávat formální jazyk. Jazyk L ⊆ Σ* rozpoznávaný automatem je množina všech slov, která automat přijímá.

Rozpoznávané jazyky: Rozpoznávané jazyky je množina jazyků, které jsou rozpoznány některým automatem. Pro výše uvedenou definici automatu jsou rozpoznávané právě regulární jazyky. Jiné definice automatů mohou vést k jiným třídám rozpoznávaných jazyků.

Alternativní definice automatu

Automaty se používají pro studium užitečných strojů pomocí matematického formalismu. Definice automatu je proto otevřená na variace podle toho, jaký „stroj z reálného světa“ chceme modelovat pomocí automatu. Lidé zkoumali mnoho druhů automatů. Varianta popsaná výše se nazývá deterministický konečný automat. Následují některé oblíbené variace v definici různých komponent automatů.

Vstup

Konečný vstup: Automat, které přijímá pouze konečné posloupnosti symbolů. Výše uvedená definice povoluje pouze konečná slova.
Nekonečný vstup: Automat, které přijímá nekonečná slova (ω-slova). Takové automaty se nazývají ω-automaty.
Stromové vstupní slovo: Místo posloupnosti symbolů může být vstupem strom symbolů. V tomto případě po načtení každého symbolu, automat načítá všechny následující symboly ve vstupním stromě. Říkáme, že automat vytvoří kopii sebe sama pro každého následovníka a každá taková kopie začíná pracovat s jedním z následnických symbolů ze stavu podle přechodové relace automatu. Takové automaty se nazývá stromový automat.
Nekonečný strom: Obě výše uvedená rozšíření mohou být zkombinována, takže automat čte stromovou strukturu s nekonečnými větvemi. Takový automat se nazývá nekonečný stromový automat

Stavy

Konečný počet stavů: Automat, který má pouze konečný počet stavů. Výše uvedená úvodní definice popisuje automaty s konečným počtem stavů.
Nekonečný počet stavů: Automat, který nemá konečný nebo dokonce ani spočetný počet stavů. Například kvantový konečný automat nebo topologický automat má nespočetně mnoho stavů.
Zásobníková paměť: Automat může také obsahovat určitý druh paměti; nejčastěji se používá paměť ve formě zásobníku, do něhož lze ukládat symboly. Tento druh automatu se nazývá zásobníkový automat

Přechodová funkce

Deterministická: Pokud pro každý aktuální stav a vstupní symbol může automat provést nejvýše jeden přechod, pak se jedná o deterministický konečný automat.
Nedeterministická: Automat, který po načtení vstupního symbolu, může přejít do libovolného z několika stavů, které mu dovoluje jeho přechodová relace. V tomto případě je přechodová funkce nahrazena přechodovou relací: Automat nedeterministicky rozhoduje, do kterého povolených stavů přejde. Takové automaty se nazývají nedeterministické automaty.
Alternace: Tato myšlenka je docela podobný stromový automat, ale ortogonální. Automat může provádět jeho více kopie na stejný další čtený symbol. Takové automaty se nazývají alternující automaty. Aby byl vstup přijat, musí podmínku přijetí splňovat všechny běhy takových kopií.

Akceptační podmínka

Přijímání konečných slov: Popsáno v neformální definici výše.
Přijímání nekonečných slov: omega automat nemůže mít koncové stavy, protože nekonečná slova nemají konec. Přijetí slova je dáno prohlížením nekonečné posloupnosti navštívených stavů při výpočtu.
Pravděpodobnostní akceptace: Automat může přijmout vstup s nějakou pravděpodobností mezi nulou a jedničkou. Příkladem automatů s pravděpodobnostním přijímáním jsou kvantový konečný automat, geometrický automat a metrický automat.

Různé kombinace výše uvedených variant dávají mnoho tříd automatů.

Teorie automatů je obor, který zkoumá vlastnosti různých typů automatů. Jedná se například o tyto otázky:

Jaká třída formálních jazyků je rozpoznávána určitým typem automatů? (rozpoznávané jazyky)
Je určitá třída automatů uzavřená vůči sjednocení, průniku nebo doplňku formálních jazyků? (uzávěrové vlastnosti)
Jak expresivní je daný typ automatu, pokud jde o rozpoznávání třídy formálních jazyků? A jaká je jejich relativní vyjadřovací síla? (hierarchie jazyků)

Teorie automatů také studuje, jestliže existuje libovolný efektivní algoritmus nebo ne, jak řešit problémy podobný následující seznam.

Přijímá automat alespoň jedno slovo? (Neprázdnost jazyka)
Je možné transformovat daný nedeterministický automat na deterministický, který přijímá stejný jazyk? (Determinizace)
Jaký je nejmenší automat, který rozpoznává daný formální jazyk? (Minimalizace).

Vztah teorie automatů a teorie formálních jazyků

Teorie automatů úzce souvisí s teorií formálních jazyků. U této teorie existuje hierarchie jazyků nazývaná Chomského hierarchie, přičemž jednotlivé třídy jazyků podle této hierarchie lze ztotožnit s různými druhy automatů:

Regulární jazyky, které je možno popsat konečnými automaty, regulárními gramatikami nebo regulárními výrazy. Příkladem regulárního jazyka je jazyk, který obsahuje předem dané slovo (například abba).

Bezkontextové jazyky, které jsou rozpoznávané bezkontextovými gramatikami nebo zásobníkovými automaty. Příkladem bezkontextového jazyka je jazyk

{aⁿbⁿ | n

\in \,\!

N} = {e, ab, aabb, aaabbb atd.}

Každý regulární jazyk je bezkontextový; zde uvedený bezkontextový jazyk však není regulární. Dokázat to lze mj. pomocí lemmatu o vkládání.

Kontextové jazyky rozpoznávané kontextovými gramatikami nebo lineárně ohraničeným Turingovým strojem. Příkladem kontextového jazyka, který není bezkontextový, je

{aⁿbⁿcⁿ | n

\in \,\!

N} = {e, abc, aabbcc, aaabbbccc atd.}

Každý bezkontextový jazyk je kontextový. Toto zdánlivě paradoxní tvrzení lze vysvětlit tak, že kontextová gramatika je gramatika, v níž každé pravidlo zaměňuje jeden symbol řetězcem v nějakém kontextu^{[pozn 1]}, zatímco „bezkontextová gramatika“ je označení pro kontextovou gramatiku, v jejímž každém pravidlu je kontext prázdný.

Gramatiky uvedené v předchozích odrážkách tvoří tzv. Chomského hierarchii.

Rekurzivně spočetné jazyky rozpoznávané všemi gramatikami nebo Turingovými stroji. Příkladem takového jazyka, který není kontextový, jsou výpočty, které vyžadují paměť diametrálně větší, než je délka vstupního slova (například na vstupu bude číslo n a program vrátí (n!)-tou (viz faktoriál) cifru z desetinné části Ludolfova čísla.

Odkazy

Poznámky

↑ Kontextová gramatika je označení pro gramatiku, která obsahuje jen pravidla tvaru např. ABCXDEF $\to$ ABCRSTDEF (kde ABC, RST, DEF jsou příklady řetězců, které ale mohou mít libovolnou délku a mohou obsahovat terminální i neterminální symboly). V tomto příkladu hrají řetězce ABC a DEF roli „kontextu“, v němž je nahrazení povoleno, odtud název „kontextová“.

Reference

V tomto článku byl použit překlad textu z článku Automata theory na anglické Wikipedii.

[1] Kontextová gramatika je označení pro gramatiku, která obsahuje jen pravidla tvaru např. ABCXDEF $\to$ ABCRSTDEF (kde ABC, RST, DEF jsou příklady řetězců, které ale mohou mít libovolnou délku a mohou obsahovat terminální i neterminální symboly). V tomto příkladu hrají řetězce ABC a DEF roli „kontextu“, v němž je nahrazení povoleno, odtud název „kontextová“.

[pozn 1]