Teorie automatů - Automata theory

Třídy automatů

(Kliknutím na každou vrstvu získáte článek na toto téma)

Automat popsaný tímto stavovým diagramem začíná ve stavu S ₁ a mění stavy podle šipek označených 0 nebo 1 podle vstupních symbolů při jejich příchodu. Dvojitý kruh označí S ₁ jako přijímající stav. Protože všechny cesty od S ₁ k sobě obsahují sudý počet šipek označených 0, tento automat přijímá řetězce obsahující sudá čísla 0 s.

Teorie automatů je studium abstraktních strojů a automatů , stejně jako výpočetních problémů, které lze pomocí nich vyřešit. Je to teorie v teoretické informatice . Slovo automaty (množné číslo automatu ) pochází z řeckého slova αὐτόματος, které znamená „samočinný, vůle, pohybující se“. Automat (automat v množném čísle) je abstraktní výpočetní zařízení s vlastním pohonem, které automaticky sleduje předem stanovený sled operací. Automat s konečným počtem stavů se nazývá konečný automat (FA) nebo konečný stavový stroj (FSM).

Obrázek vpravo ukazuje stroj s konečným stavem , který patří ke známému typu automatu. Tento automat se skládá ze stavů (na obrázku znázorněných kruhy) a přechodů (znázorněných šipkami). Když automat vidí symbol vstupu, provede přechod (nebo skok) do jiného stavu podle své přechodové funkce , která jako argumenty bere předchozí stav a aktuální vstupní symbol.

Teorie automatů úzce souvisí s teorií formálních jazyků . V této souvislosti se automaty používají jako konečné reprezentace formálních jazyků, které mohou být nekonečné. Automaty jsou často klasifikovány podle třídy formálních jazyků, které dokážou rozpoznat, jako v Chomského hierarchii , která popisuje vnořovací vztah mezi hlavními třídami automatů. Automaty hrají hlavní roli v teorii výpočtu , konstrukci kompilátoru , umělé inteligenci , analýze a formálním ověřování .

Dějiny

Teorie abstraktních automatů byla vyvinuta v polovině 20. století v souvislosti s konečnými automaty . Teorie automatů byla zpočátku považována za odvětví teorie matematických systémů , studovala chování systémů diskrétních parametrů. Rané práce v teorii automatů se lišily od předchozích prací na systémech tím, že k popisu informačních systémů používaly abstraktní algebru, a nikoli materiální systémy, diferenciální počet . Teorie konečného snímače byla vyvinuta pod různými názvy různými výzkumnými komunitami. Dřívější disciplína Turingových strojů byla také zahrnuta v disciplíně spolu s novými formami automatů s nekonečným stavem, jako jsou tlačné automaty .

V roce 1956 vyšla publikace Automata Studies , která shromažďovala práci vědců včetně Clauda Shannona , W. Rosse Ashbyho , Johna von Neumanna , Marvina Minskyho , Edwarda F. Moora a Stephena Cole Kleene . Vydáním tohoto svazku „teorie automatů vznikla jako relativně autonomní disciplína“. Kniha zahrnovala Kleeneův popis souboru pravidelných akcí nebo pravidelných jazyků a relativně stabilní měřítko složitosti programů Turingova stroje od Shannona. Ve stejném roce Noam Chomsky popsal Chomského hierarchii , korespondenci mezi automaty a formálními gramatikami , a Ross Ashby vydal Úvod do kybernetiky , dostupnou učebnici vysvětlující automaty a informace pomocí základní teorie množin.

Studium lineárních automatů vedlo k Myhill-Nerodeově větě , která dává nezbytnou a dostatečnou podmínku pro to, aby byl formální jazyk pravidelný, a přesný počet stavů v minimálním stroji pro daný jazyk. Čerpání lemma pro regulární jazyky , také užitečná v pravidelnosti důkazy, bylo prokázáno v tomto období od Michaela O. Rabin a Dana Scott spolu s výpočetní ekvivalence deterministické a nedeterministických konečných automatů.

V 60. letech 20. století vznikl soubor algebraických výsledků známý jako „teorie struktury“ nebo „teorie algebraického rozkladu“, který se zabýval realizací sekvenčních strojů z menších strojů propojením. Zatímco jakýkoli konečný automat lze simulovat pomocí sady univerzálních hradel , vyžaduje to, aby simulační obvod obsahoval smyčky libovolné složitosti. Teorie struktury se zabývá realizovatelností strojů „bez smyčky“. V šedesátých letech se také formovala teorie výpočetní složitosti . Na konci tohoto desetiletí byla teorie automatů považována za „čistou matematiku počítačové vědy“.

Automaty

Následuje obecná definice automatu, která omezuje širší definici systému na jeden, který je považován za jednající v diskrétních časových krocích, přičemž jeho stavové chování a výstupy jsou v každém kroku definovány neměnnými funkcemi pouze jeho stavu a vstupu.

Neformální popis

Automat běží, když dostane určitou posloupnost vstupů v diskrétních (individuálních) časových krocích nebo krocích. Automat zpracovává jeden vstup vybraný ze sady symbolů nebo písmen , která se nazývá vstupní abeceda . Symboly přijaté automatem jako vstup v jakémkoli kroku jsou posloupností symbolů nazývaných slova . Automat má sadu stavů . V každém okamžiku během běhu automatu je automat v jednom ze svých stavů. Když automat přijme nový vstup, přejde do jiného stavu (nebo přechodů ) na základě přechodové funkce, která jako parametry bere předchozí stav a aktuální vstupní symbol. Současně další funkce zvaná výstupní funkce produkuje symboly z výstupní abecedy , také podle předchozího stavu a aktuálního vstupního symbolu. Automat čte symboly vstupního slova a přechází mezi stavy, dokud není slovo přečteno úplně, pokud má konečnou délku, v tomto okamžiku se automat zastaví . Stav, ve kterém se automat zastaví, se nazývá konečný stav .

K prozkoumání možných stavových/vstupních/výstupních sekvencí v automatu pomocí formální jazykové teorie lze stroji přiřadit počáteční stav a sadu přijímajících stavů . Potom, v závislosti na tom, zda běh začínající od počátečního stavu končí v přijímajícím stavu, lze říci, že automat přijímá nebo odmítá vstupní sekvenci. Množina všech slov přijatých automatem se nazývá jazyk rozpoznaný automatem . Známým příkladem stroje rozpoznávajícího jazyk je elektronický zámek, který přijímá nebo odmítá pokusy o zadání správného kódu.

Formální definice

Automat

Automat může být formálně reprezentován 5-ticí , kde: ${\ Displaystyle M = \ langle \ Sigma, \ Gamma, Q, \ delta, \ lambda \ rangle}$

• ${\ displaystyle \ Sigma}$je konečná sada symbolů , nazývaná vstupní abeceda automatu,
• ${\ displaystyle \ Gamma}$je další konečná sada symbolů, nazývaná výstupní abeceda automatu,
• ${\ displaystyle Q}$je sada států ,
• ${\ Displaystyle \ delta}$je funkce dalšího stavu nebo přechodová funkce mapující páry stav-vstup do následnických stavů,${\ Displaystyle \ delta: Q \ times \ Sigma \ to Q}$
• ${\ Displaystyle \ lambda}$je funkce dalšího výstupu mapující páry stav-vstup na výstupy.${\ Displaystyle \ lambda: Q \ times \ Sigma \ to \ Gamma}$

Pokud je konečný, pak je konečný automat .${\ displaystyle Q}$${\ displaystyle M}$

Vstupní slovo

Automat čte konečný řetězec symbolů , kde se nazývá vstupní slovo . Množina všech slov je označena .${\ displaystyle a_ {1} a_ {2} ... a_ {n}}$${\ displaystyle a_ {i} \ in \ Sigma}$${\ displaystyle \ Sigma ^{*}}$

Běh

Sekvence stavů , kde taková, že pro , je běh automatu na vstupu začínajícím ze stavu . Jinými slovy, zprvu je automat ve výchozím stavu a přijímá vstup . Pro a každý následující ve vstupním řetězci, automat vybere další stavu podle funkce přechodu , dokud poslední symbol byla přečtena, opuštěním stroje v konečném stavu z hlediska . Podobně v každém kroku automat vydává výstupní symbol podle výstupní funkce .${\ displaystyle q_ {0}, q_ {1}, ... q_ {n}}$${\ displaystyle q_ {i} \ v Q}$${\ displaystyle q_ {i} = \ delta (q_ {i-1}, a_ {i})}$${\ Displaystyle 0 <i \ leq n}$${\ displaystyle a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^{*}}$${\ displaystyle q_ {0}}$${\ displaystyle q_ {0}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {i}}$${\ displaystyle q_ {i}}$${\ Displaystyle \ delta (q_ {i-1}, a_ {i})}$${\ displaystyle a_ {n}}$${\ displaystyle q_ {n}}$${\ Displaystyle \ lambda (q_ {i-1}, a_ {i})}$

Funkce přechodu je induktivně rozšířena na popis chování stroje při podávání celých vstupních slov. Pro prázdný řetězec , pro všechny státy , a pro smyčce , kde je poslední symbol a je (možná prázdná) zbytek řetězce, . Výstupní funkce může být rozšířena podobně na , což poskytuje úplný výstup stroje při spuštění na slovo ze stavu .${\ Displaystyle \ delta}$${\ displaystyle {\ overline {\ delta}}: Q \ times \ Sigma ^{*} \ to Q}$${\ displaystyle \ varepsilon}$${\ displaystyle {\ overline {\ delta}} (q, \ varepsilon) = q}$${\ displaystyle q}$${\ displaystyle wa}$${\ displaystyle a}$${\ displaystyle w}$${\ Displaystyle {\ overline {\ delta}} (q, wa) = \ delta ({\ overline {\ delta}} (q, w), a)}$${\ Displaystyle \ lambda}$${\ displaystyle {\ overline {\ lambda}} (q, w)}$${\ displaystyle w}$${\ displaystyle q}$

Přijímač

Aby bylo možné studovat automat s teorií formálních jazyků , může být automat považován za akceptor , který nahradí výstupní abecedu a funkci a za ${\ displaystyle \ Gamma}$${\ Displaystyle \ lambda}$

• ${\ displaystyle q_ {0} \ v Q}$, určený počáteční stav a
• ${\ displaystyle F}$, množina stavů (tj. ) nazývaných stavy přijetí .${\ displaystyle Q}$${\ displaystyle F \ subseteq Q}$

To umožňuje definovat následující:

Přijetí slova

Slovo je pro automat přijímací slovo , pokud je stroj po konzumaci celého řetězce v přijímacím stavu.${\ Displaystyle w = a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^{*}}$${\ displaystyle {\ overline {\ delta}} (q_ {0}, w) \ v F}$${\ displaystyle w}$

Rozpoznaný jazyk

Jazyk uznán podle automatu je množina všech slov, která jsou akceptovaných automatem, .${\ displaystyle L \ subseteq \ Sigma ^{*}}$ ${\ Displaystyle L = \ {w \ in \ Sigma ^{*} \ | \ {\ overline {\ delta}} (q_ {0}, w) \ in F \}}$

Rozpoznatelné jazyky

Tyto rozeznatelné jazyky jsou sada jazyků, které jsou uznávány některými automatem. U konečných automatů jsou rozpoznatelnými jazyky běžné jazyky . U různých typů automatů jsou rozpoznatelné jazyky odlišné.

Variantní definice automatů

Automaty jsou definovány ke studiu užitečných strojů podle matematického formalismu. Definice automatu je tedy otevřena variacím podle „stroje skutečného světa“, který chceme modelovat pomocí automatu. Lidé studovali mnoho variant automatů. Následuje několik oblíbených variací v definici různých komponent automatů.

Vstup

• Konečný vstup : Automat, který přijímá pouze konečnou posloupnost symbolů. Výše uvedená úvodní definice zahrnuje pouze konečná slova.
• Nekonečný vstup : Automat, který přijímá nekonečná slova ( ω-slova ). Takové automaty se nazývají ω-automaty .
• Vstup stromového slova : Vstupem může být strom symbolů místo posloupnosti symbolů. V tomto případě po přečtení každého symbolu automat přečte všechny nástupnické symboly ve vstupním stromu. Říká se, že automat vytvoří jednu kopii sebe pro každého následníka a každá taková kopie začne běžet na jednom ze symbolů nástupce ze stavu podle přechodového vztahu automatu. Takovému automatu se říká stromový automat .
• Nekonečný stromový vstup  : Obě výše uvedená rozšíření lze kombinovat, takže automat čte stromovou strukturu s (ne) konečnými větvemi. Takovému automatu se říká nekonečný stromový automat

Státy

• Jeden stav : Automat s jedním stavem, nazývaný také kombinační obvod , provádí transformaci, která může implementovat kombinační logiku .
• Konečné stavy : Automat, který obsahuje pouze konečný počet stavů.
• Nekonečné stavy : Automat, který nemusí mít konečný počet stavů nebo dokonce počitatelný počet stavů. K poskytnutí konečných popisů těmto strojům lze použít různé druhy abstraktní paměti.
• Paměť zásobníku : Automat může také obsahovat nějakou další paměť ve formě hromádky, do které lze vkládat a vysouvat symboly. Tento druh automatu se nazývá pushdown automat
• Paměť fronty : Automat může mít paměť ve formě fronty . Takový stroj se nazývá frontový stroj a je Turing-kompletní.
• Paměť pásek : Vstupy a výstupy automatů jsou často popisovány jako vstupní a výstupní pásky . Některé stroje mají další pracovní pásky , včetně Turingova stroje , lineárního ohraničeného automatu a převodníku log-prostoru .

Přechodová funkce

• Deterministický : Pokud pro daný aktuální stav a vstupní symbol může automat přeskočit pouze do jednoho a pouze jednoho stavu, jedná se o deterministický automat .
• Nedeterministický : Automat, který po přečtení vstupního symbolu může přeskočit do kteréhokoli z několika stavů, jak je licencováno jeho přechodovým vztahem. Všimněte si, že termín přechodová funkce je nahrazen přechodovým vztahem: Automat nedeterministicky se rozhodne skočit do jedné z povolených voleb. Takovým automatům se říká nedeterministické automaty .
• Střídání : Tato myšlenka je velmi podobná stromovému automatu, ale ortogonální. Automat může spouštět více kopií na stejném dalším symbolu čtení. Takovým automatům se říká střídavé automaty . Podmínka přijetí musí splňovat všechny běhy takových kopií, aby přijala zadání.

Podmínka přijetí

• Přijetí konečných slov : Stejné, jak je popsáno ve výše uvedené neformální definici.
• Přijetí nekonečných slov : omega automat nemůže mít konečné stavy, protože nekonečná slova nikdy nekončí. O přijetí slova spíše rozhoduje pohled na nekonečnou posloupnost navštívených stavů během běhu.
• Pravděpodobnostní přijetí : Automat nemusí přísně přijímat nebo odmítat zadání. Může přijmout vstup s určitou pravděpodobností mezi nulou a jedničkou. Například kvantový konečný automat, geometrický automat a metrický automat mají pravděpodobnostní akceptaci.

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

Teorie automatů je předmět, který studuje vlastnosti různých typů automatů. Následující otázky jsou například studovány na daný typ automatů.

• Kterou třídu formálních jazyků rozpoznávají některé typy automatů? (Rozpoznatelné jazyky)
• Jsou některé automaty uzavřeny pod sjednocením, průnikem nebo doplňováním formálních jazyků? (Vlastnosti uzavření)
• Jak expresivní je typ automatů, pokud jde o rozpoznávání třídy formálních jazyků? A jejich relativní vyjadřovací síla? (Jazyková hierarchie)

Teorie automatů také studuje existenci nebo neexistenci jakýchkoli účinných algoritmů k řešení problémů podobných následujícímu seznamu:

• Přijímá automat nějaké vstupní slovo? (Kontrola prázdnoty)
• Je možné transformovat daný nedeterministický automat na deterministický automat bez změny rozpoznatelného jazyka? (Determinizace)
• Jaký je pro daný formální jazyk nejmenší automat, který jej rozpoznává? ( Minimalizace )

Třídy automatů

Následuje neúplný seznam typů automatů.

Diskrétní, spojité a hybridní automaty

Teorie automatů obvykle popisuje stavy abstraktních strojů, ale existují diskrétní automaty, analogové automaty nebo spojité automaty nebo hybridní diskrétní spojité automaty , které používají digitální data, analogová data nebo spojitý čas, respektive digitální a analogová data.

Hierarchie z hlediska pravomocí

Následuje neúplná hierarchie, pokud jde o pravomoci různých typů virtuálních počítačů. Hierarchie odráží vnořené kategorie jazyků, které jsou stroje schopné akceptovat.

Aplikace

Každý model v teorii automatů hraje důležitou roli v několika aplikovaných oblastech. Konečné automaty se používají při zpracování textu, překladačích a návrhu hardwaru. Bezkontextová gramatika (CFG) se používá v programovacích jazycích a umělé inteligenci. CFG byly původně používány při studiu lidských jazyků. V oblasti umělého života se používají mobilní automaty , nejznámějším příkladem je Hra o život Johna Conwaye . Některé další příklady, které by mohly být vysvětleny pomocí teorie automatů v biologii, zahrnují růst měkkých měkkýšů a šišek a pigmentace. Když půjdeme dále, někteří vědci zastávají teorii naznačující, že celý vesmír je počítán nějakým diskrétním automatem. Tato myšlenka vznikla v díle Konrada Zuse a v Americe ji propagoval Edward Fredkin . Automatika se také objevuje v teorii konečných polí: množina neredukovatelných polynomů, které lze zapsat jako složení polynomů stupně dva, je ve skutečnosti regulárním jazykem. Dalším problémem, pro který lze automaty použít, je indukce regulárních jazyků .

Simulátory automatů

Simulátory automatů jsou pedagogické nástroje používané k výuce, učení a výzkumu teorie automatů. Simulátor automatů bere jako vstup popis automatu a poté simuluje jeho práci pro libovolný vstupní řetězec. Popis automatu lze zadat několika způsoby. Automat může být definován v symbolickém jazyce nebo jeho specifikace může být zadána v předem navrženém tvaru nebo může být nakreslen jeho přechodový diagram kliknutím a tažením myši. Mezi dobře známé automaty patří Turingův svět, JFLAP, VAS, TAGS a SimStudio.

Spojení s teorií kategorií

Podle klasifikace automatů do různých typů popsaných v předchozí části lze definovat několik různých kategorií automatů. Matematická kategorie deterministických automatů, sekvenčních strojů nebo sekvenčních automatů a Turingových strojů s homomorfismy automatů definujících šipky mezi automaty je karteziánská uzavřená kategorie , která má jak kategorické limity, tak mezní limity. Homomorfismus automatů mapuje pětinásobek automatu A _i na pětinásobek jiného automatu A _j . Homomorfismy automatů lze také považovat za transformace automatů nebo za homomorfismy semigroup, když je stavový prostor S automatu definován jako poloskupina S _g . Monoidy jsou také považovány za vhodné nastavení pro automaty v monoidálních kategoriích .

Kategorie variabilních automatů

Dalo by se také definovat variabilní automat , ve smyslu Norberta Wienera ve své knize The Human Use of Human Beings via the endomorphisms . Potom je možné ukázat, že takové homomorfismy variabilních automatů tvoří matematickou skupinu. V případě nedeterministických nebo jiných složitých druhů automatů se však z této druhé sady endomorfismů může stát variabilní automat grupo . V nejobecnějším případě jsou tedy kategorie variabilních automatů jakéhokoli druhu kategoriemi skupinových nebo skupinových kategorií . Kromě toho je pak kategorie reverzibilních automatů kategorie 2 a také podkategorie kategorie 2 grupoidů neboli kategorie groupoidů. ${\ displaystyle A_ {i} \ do A_ {i}}$

Viz také

• Booleovský diferenciální počet

Reference

Další čtení

• John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman (2000). Úvod do teorie automatů, jazyků a výpočetní techniky (2. vyd.). Pearsonovo vzdělávání. ISBN 978-0-201-44124-6.Správa CS1: používá parametr autorů ( odkaz )
• Michael Sipser (1997). Úvod do teorie výpočtů . Publikování PWS. ISBN 978-0-534-94728-6.Část první: Automaty a jazyky, kapitoly 1–2, s. 29–122. Oddíl 4.1: Rozhodovatelné jazyky, s. 152–159. Oddíl 5.1: Nerozhodnutelné problémy z jazykové teorie, s. 172–183.
• Elaine Richová (2008). Automaty, počitatelnost a složitost: teorie a aplikace . Pearson. ISBN 978-0-13-228806-4.
• Salomaa, Arto (1985). Výpočty a automaty . Encyklopedie matematiky a její aplikace. 25 . Cambridge University Press . ISBN 978-0-521-30245-6. Zbl  0565.68046 .
• Anderson, James A. (2006). Teorie automatů s moderními aplikacemi . S příspěvky Toma Heada. Cambridge: Cambridge University Press . ISBN 978-0-521-61324-8. Zbl  1127.68049 .
• Conway, JH (1971). Pravidelné algebry a konečné stroje . Série matematiky Chapman a Hall. Londýn: Chapman & Hall . Zbl  0231.94041 .
• John M. Howie (1991) Automata and Languages , Clarendon Press ISBN  0-19-853424-8 MR 1254435
• Sakarovitch, Jacques (2009). Prvky teorie automatů . Přeložil z francouzštiny Reuben Thomas. Cambridge University Press . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
• James P. Schmeiser , David T. Barnard (1995). Vytvoření pořadí analýzy shora dolů s analýzou zdola nahoru . Elsevier Severní Holandsko.Správa CS1: používá parametr autorů ( odkaz )
• Igor Aleksander , F. Keith Hanna (1975). Teorie automatů: Inženýrský přístup . New York: Crane Russak. ISBN 978-0-8448-0657-0.Správa CS1: používá parametr autorů ( odkaz )
• Marvin Minsky (1967). Výpočet: Konečné a nekonečné stroje . Princeton, New Jersey: Prentice Hall.
• John C. Martin (2011). Úvod do jazyků a teorie výpočtů . New York, NY 10020: McGraw Hill. ISBN 978-0-07-319146-1.CS1 maint: location ( link )

externí odkazy

• Visual Automata Simulator , nástroj pro simulaci, vizualizaci a transformaci automatů s konečným stavem a Turingových strojů, Jean Bovet
• JFLAP
• dk.brics.automaton
• libfa