V tomto článku prozkoumáme fascinující život a dílo Teorie automatů, jedince, který zanechal nesmazatelnou stopu v historii. Od svých skromných začátků až po trvalý dopad na dnešní svět je Teorie automatů předmětem obdivu, studia a sporů. Na těchto stránkách se ponoříme do jeho odkazu, prozkoumáme jeho vliv v různých oblastech, jeho roli v zásadních okamžicích historie a ponaučení, které můžeme čerpat z jeho zkušeností. Připravte se na vzrušující cestu životem a příspěvky Teorie automatů a zjistěte, proč jeho příběh nadále rezonuje v našich srdcích a myslích.
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.
Následující popis jednoho typu automatu vysvětluje koncepty používané v teorii automatů.
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ů.
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ů.
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:
Teorie automatů také studuje, jestliže existuje libovolný efektivní algoritmus nebo ne, jak řešit problémy podobný následující seznam.
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
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
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.
V tomto článku byl použit překlad textu z článku Automata theory na anglické Wikipedii.