Teorie automatů - Automata theory
Teorie automatů je studium abstraktní stroje a automaty, stejně jako výpočetní problémy které lze vyřešit jejich použitím. Je to teorie v teoretická informatika. Slovo automaty (množné číslo automat) pochází z řeckého slova αὐτόματα, což znamená „vlastní výroba“.
Obrázek vpravo ilustruje a konečný stavový stroj, který patří k známému typu automatu. Tento automat se skládá z státy (znázorněné na obrázku kruhy) a přechody (znázorněné šipkami). Když automat vidí symbol vstupu, provede přechod (nebo skok) do jiného stavu podle svého přechodová funkce, který bere aktuální stav a poslední symbol jako své vstupy.
Teorie automatů úzce souvisí s formální jazyk teorie. Automat je konečné vyjádření formálního jazyka, kterým může být nekonečná množina. Automaty jsou často klasifikovány podle třídy formálních jazyků, které dokážou rozpoznat, což obvykle ilustruje Chomského hierarchie, který popisuje vztahy mezi různými jazyky a druhy formalizované logiky.
Automaty hrají hlavní roli v teorie výpočtu, konstrukce kompilátoru, umělá inteligence, analýza a formální ověření.
Automaty
Následuje úvodní definice jednoho typu automatu, který se pokouší pomoci člověku pochopit základní pojmy zahrnuté v teorii / teorii automatů.
Velmi neformální popis
Automat je konstrukce vyrobená z státy navržen tak, aby určil, zda má být vstup přijat nebo odmítnut. Vypadá to hodně jako základní desková hra, kde každé místo na desce představuje stav. Každý stát má informace o tom, co má dělat, když stroj přijme vstup (opět spíše jako co dělat, když přistanete na Jít do vězení místo v populární deskové hře). Když stroj přijme nový vstup, podívá se na stav a vybere nové místo na základě informací o tom, co má dělat, když tento vstup přijme v tomto stavu. Pokud již nejsou žádné další vstupy, automat se zastaví a prostor, ve kterém se nachází, když dokončí, určuje, zda automat tuto konkrétní sadu vstupů přijme nebo odmítne.
Neformální popis
Automat běží když je dána nějaká posloupnost vstupy diskrétní (individuální) časové kroky nebo kroky. Automat zpracovává jeden vstup vybraný ze sady symboly nebo písmena, který se nazývá abeceda. Symboly přijímané automatem jako vstup v kterémkoli kroku jsou konečnou posloupností volaných symbolů slova. Automat má konečnou množinu státy. V každém okamžiku během běhu automatu je automat v jeden z jeho států. Když automat obdrží nový vstup, přesune se do jiného stavu (nebo přechody) na základě funkce, která bere aktuální stav a symbol jako parametry. 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 funkce přechodu, dokud není slovo přečteno úplně. Po přečtení vstupního slova se říká, že se automat zastavil. Stav, ve kterém se automat zastaví, se nazývá konečný stav. V závislosti na konečném stavu se říká, že automat přijímá nebo odmítá vstupní slovo. Existuje podmnožina stavů automatu, která je definována jako množina přijímající státy. Pokud je konečný stav stav přijímající, pak automat přijímá slovo. Jinak je to slovo zamítnuto. Sada všech slov přijímaných automatem se nazývá Jazyk rozpoznáno automatem.
Stručně řečeno, automat je a matematický objekt který vezme slovo jako vstup a rozhodne se, zda jej přijme nebo odmítne. Vzhledem k tomu, že všechny výpočtové problémy lze redukovat na otázku přijetí / odmítnutí na vstupech, (všechny problémové instance lze vyjádřit v konečné délce symbolů)[Citace je zapotřebí ], teorie automatů hraje klíčovou roli v výpočetní teorie.
Formální definice
- Automat
definice konečné automaty
- Vstupní slovo
- Automat čte konečnou tětiva symbolů a1,A2, ...., an , kdei ∈ Σ, kterému se říká an vstupní slovo. Sada všech slov je označena Σ *.
- Běh
- Posloupnost stavů q0, q1, q2, ...., qn, kde qi ∈ Q takové, že q0 je počáteční stav a qi = δ (qi-1,Ai) pro 0 běh automatu na vstupním slově w = a1,A2, ...., an ∈ Σ *. Jinými slovy, automat je nejprve v počátečním stavu q0, a potom automat načte symboly vstupního slova v pořadí. Když automat načte symbol ai skočí do stavu qi = δ (qi-1,Ai). qn se říká, že konečný stav běhu.
- Přijímající slovo
- Automat q přijme slovo w ∈ Σ *, pokud qn ∈ F.
- Uznávaný jazyk
- Automat dokáže rozpoznat a formální jazyk. Jazyk L ⊆ Σ * rozpoznávaný automatem je množina všech slov, která automat přijímá.
- Rozpoznatelné jazyky
- The rozpoznatelné jazyky jsou sada jazyků, které jsou rozpoznávány nějakým automatem. U výše uvedené definice automatů jsou rozpoznatelné jazyky běžné jazyky. Pro různé definice automatů jsou rozpoznatelné jazyky odlišné.
Definice variant automatů
Automaty jsou definovány pro studium užitečných strojů pod matematickým formalismem. Definice automatu je tedy otevřená variacím podle „stroje reálného světa“, který chceme modelovat pomocí automatu. Lidé studovali mnoho variant automatů. Nejstandardnější varianta, která je popsána výše, se nazývá a deterministický konečný automat. Následuje několik populární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 do stromu: Vstup může být a strom symbolů místo posloupnosti symbolů. V tomto případě po přečtení každého symbolu automat čte všechny nástupnické symboly ve vstupním stromu. Říká se, že automat vytvoří jednu kopii sama o sobě pro každého následníka a každá taková kopie začíná běžet na jednom z následnických symbolů ze státu podle přechodového vztahu automatu. Takový automat se nazývá a stromový automat.
- Nekonečný vstup do stromu : Dvě výše uvedená rozšíření lze kombinovat, takže automat načte stromovou strukturu s (ne) konečnými větvemi. Takový automat se nazývá automat nekonečných stromů
- Státy
- Konečné stavy: Automat, který obsahuje pouze konečný počet stavů. Výše uvedená úvodní definice popisuje automaty s konečným počtem stavů.
- Nekonečné stavy: Automat, který nemusí mít konečný počet stavů, nebo dokonce a počitatelný počet států. Například kvantový konečný automat nebo topologický automat má nespočetné nekonečno států.
- Zásobník paměti: Automat může také obsahovat nějakou další paměť ve formě a zásobník ve kterém lze symboly tlačit a vysouvat. Tento druh automatu se nazývá a zasunovací automat
- Funkce přechodu
- Deterministický: Pokud pro daný aktuální stav a vstupní symbol může automat skákat pouze do jednoho a pouze jednoho stavu, pak je to a deterministický automat.
- Nedeterministické: Automat, který po přečtení vstupního symbolu může přeskočit do kteréhokoli z mnoha států, 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 možností. Takové automaty se nazývají nedeterministické automaty.
- Střídání: Tato myšlenka je docela podobná stromovému automatu, ale ortogonální. Automat může spustit svůj více kopií na stejný další přečtený symbol. Takové automaty se nazývají střídavé automaty. Podmínka přijetí musí uspokojit všechny takové běhy kopie přijmout vstup.
- Podmínka přijetí
- Přijímání konečných slov: Stejné, jak je popsáno v neformální definici výše.
- Přijímání nekonečných slov: an Omega automat nemůže mít konečné stavy, protože nekonečná slova nikdy nekončí. O přijetí slova se rozhoduje spíše pohledem na nekonečný sled navštívených států během běhu.
- Pravděpodobné přijetí: Automat nemusí přísně přijímat nebo odmítat vstup. S některými může přijmout vstup pravděpodobnost mezi nulou a jednou. Například kvantový konečný automat, geometrický automat a metrický automat mít pravděpodobnostní přijetí.
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 o daném typu automatů.
- Která třída formálních jazyků je rozpoznatelná nějakým typem automatů? (Rozpoznatelné jazyky)
- Jsou určité automaty Zavřeno v rámci unie, křižovatky nebo doplňování formálních jazyků? (Uzavírací vlastnosti)
- Jak výrazný je typ automatů z hlediska rozpoznávání třídy formálních jazyků? A jejich relativní expresivní síla? (Jazyková hierarchie)
Teorie automatů také studuje existenci nebo neexistenci jakékoli efektivní algoritmy vyřešit problémy podobné 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 beze změny rozpoznatelného jazyka? (Stanovení)
- Jaký je nejmenší automat pro daný formální jazyk, který jej rozpoznává? (Minimalizace )
Třídy automatů
Následuje neúplný seznam typů automatů.
Automat | Rozpoznatelný jazyk |
---|---|
Nedeterministický / deterministický stroj s konečným stavem (FSM) | běžné jazyky |
Deterministický posunovací automat (DPDA) | deterministické bezkontextové jazyky |
Pushdown automat (PDA) | bezkontextové jazyky |
Lineárně ohraničený automat (LBA) | kontextově citlivé jazyky |
Turingův stroj | rekurzivně vyčíslitelné jazyky |
Deterministický Büchi automat | ω-omezit jazyky |
Nedeterministický Büchi automat | ω-běžné jazyky |
Rabinov automat, Streett automat, Paritní automat, Mullerův automat |
Diskrétní, spojité a hybridní automaty
Teorie automatů obvykle popisuje stavy abstraktních strojů, ale existují analogové automaty nebo spojité automaty nebo hybridní diskrétní spojité automaty, která používají analogová data, nepřetržitý čas nebo obojí.
Hierarchie z hlediska pravomocí
Následuje neúplná hierarchie, pokud jde o pravomoci různých typů virtuálních strojů. Hierarchie odráží vnořené kategorie jazyků, které jsou stroje schopny přijmout.[1]
Automat |
---|
Deterministický konečný automat (DFA) - nejnižší výkon (stejný výkon) (stejný výkon) |
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, kompilátorech a návrhu hardwaru. Bezkontextová gramatika (CFG) se používají v programovacích jazycích a umělé inteligenci. Původně se CFG používaly při studiu lidských jazyků. Mobilní automaty jsou používány v oblasti biologie, nejběžnějším příkladem je John Conway je Hra o život. Některé další příklady, které lze vysvětlit pomocí teorie automatů v biologii, zahrnují růst měkkýšů a šišek a pigmentace. Jde dále, teorii, která naznačuje, že celý vesmír je počítán jakýmsi diskrétním automatem, obhajují někteří vědci. Myšlenka vznikla v díle Konrad Zuse, a byl propagován v Americe Edward Fredkin. Automaty se objevují také v teorii konečných polí: množina neredukovatelných polynomů, které lze zapsat jako složení polynomů stupně dva, je ve skutečnosti běžným jazykem.[2]Dalším problémem, pro který lze automaty použít, je uvedení běžný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 lze definovat v a symbolický jazyk nebo lze jeho specifikaci zadat v předem určené podobě nebo jeho přechodový diagram nakreslit kliknutím a tažením myši. Známé simulátory automatů zahrnují Turing's World, JFLAP, VAS, TAGS a SimStudio.[3]
Spojení s teorií kategorií
Lze definovat několik odlišných Kategorie automatů[4] podle klasifikace automatů do různých typů popsaných v předchozí části. Matematická kategorie deterministických automatů, sekvenční stroje nebo sekvenční automatya Turingovy stroje s homomorfismy automatů definující šipky mezi automaty jsou a Kartézská uzavřená kategorie,[5][6] má jak kategorické limity, tak kolimity. Homomorfismus automatů mapuje pětinásobek automatu Ai na pětinásobek jiného automatu Aj.[7] Homomorfismy automatů lze také považovat za transformace automatů nebo jako poloskupinové homomorfismy, když stavový prostor, S, automatu je definován jako poloskupina SG. Monoidy jsou také považovány za vhodné nastavení pro automaty ve Windows monoidní kategorie.[8][9][10]
- Kategorie proměnných automatů
Dalo by se také definovat a variabilní automat, ve smyslu Norbert Wiener ve své knize o Lidské použití lidských bytostí přes endomorfismy . Potom lze ukázat, že takové homomorfismy proměnných automatů tvoří matematickou skupinu. V případě nedeterministických nebo jiných složitých druhů automatů se druhá sada endomorfismů může stát variabilní automat grupoid. Proto jsou v nejobecnějším případě kategorie proměnných automatů jakéhokoli druhu kategorie grupoidů nebo skupinové kategorie. Kategorie reverzibilních automatů je navíc a 2-kategorie, a také podkategorii 2-kategorie grupoidů nebo kategorie grupoidů.
Dějiny
Teorie automatů byla vyvinuta v polovině 20. století v souvislosti s konečné automaty.[11]
Viz také
Reference
- ^ Yan, Song Y. (1998). Úvod do formálních jazyků a výpočtu strojů. Singapur: World Scientific Publishing Co. Pte. Ltd. str. 155–156. ISBN 9789810234225.
- ^ Ferraguti, A .; Micheli, G .; Schnyder, R. (2018), Neredukovatelné kompozice polynomů stupně dva přes konečná pole mají pravidelnou strukturu, Quarterly Journal of Mathematics, 69, Oxford University Press, s. 1089–1099, arXiv:1701.06040, doi:10.1093 / qmath / hay015, S2CID 3962424
- ^ Chakraborty, P .; Saxena, P. C .; Katti, C. P. (2011). „Padesát let simulace automatů: recenze“. ACM nájezdy. 2 (4): 59–70. doi:10.1145/2038876.2038893. S2CID 6446749.
- ^ Jirí Adámek a Věra Trnková. 1990. Automaty a algebry v kategoriích. Akademičtí vydavatelé Kluwer: Dordrecht a Praha
- ^ Mac Lane, Saunders (1971). Kategorie pro Working Mathematician. New York: Springer. ISBN 9780387900360.
- ^ Kartézská uzavřená kategorie Archivováno 16. listopadu 2011 v Wayback Machine
- ^ Kategorie automatů Archivováno 15. září 2011 v Wayback Machine
- ^ http://www.math.cornell.edu/~worthing/asl2010.pdf James Worthington.2010. Určování, zapomínání a automaty v monoidních kategoriích. Výroční zasedání ASL North American, 17. března 2010
- ^ Aguiar, M. a Mahajan, S.2010. „Monoidní funktory, druhy a Hopfovy algebry“.
- ^ Meseguer, J., Montanari, U .: 1990 Petriho sítě jsou monoidy. Informace a výpočet 88:105–155
- ^ Mahoney, Michael S. "Struktury výpočtu a matematická struktura přírody". Rutherford Journal. Citováno 2020-06-07.
Další čtení
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Úvod do teorie automatů, jazyků a výpočtu (2. vyd.). Pearson Education. ISBN 978-0-201-44124-6.CS1 maint: používá parametr autoři (odkaz)
- Michael Sipser (1997). Úvod do teorie výpočtu. PWS Publishing. ISBN 978-0-534-94728-6. Část první: Automaty a jazyky, kapitoly 1–2, s. 29–122. Oddíl 4.1: Rozhodnutelné jazyky, s. 152–159. Část 5.1: Nerozhodnutelné problémy z jazykové teorie, str. 172–183.
- Elaine Rich (2008). Automaty, vypočítatelnost a složitost: teorie a aplikace. Pearson. ISBN 978-0-13-228806-4.
- Salomaa, Arto (1985). Výpočet 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, J.H. (1971). Pravidelné algebry a konečné stroje. Chapman and Hall Mathematics Series. Londýn: Chapman & Hall. Zbl 0231.94041.
- John M. Howie (1991) Automaty a jazyky, Clarendon Press ISBN 0-19-853424-8 PAN1254435
- Sakarovitch, Jacques (2009). Základy teorie automatů. Z francouzštiny přeložil Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
- James P. Schmeiser, David T. Barnard (1995). Produkce objednávky syntézy shora dolů s analýzou zdola nahoru. Elsevier Severní Holandsko.CS1 maint: používá parametr autoři (odkaz)
- Igor Aleksander, F. Keith Hanna (1975). Teorie automatů: Inženýrský přístup. New York: Crane Russak. ISBN 978-0-8448-0657-0.CS1 maint: používá parametr autoři (odkaz)
- Marvin Minsky (1967). Výpočet: Konečné a nekonečné stroje. Princeton, N.J .: Prentice Hall.
- John C. Martin (2011). Úvod do jazyků a teorie výpočtu. New York, NY 10020: McGraw Hill. ISBN 978-0-07-319146-1.CS1 maint: umístění (odkaz)
externí odkazy
- Simulátor vizuálních automatů „Nástroj pro simulaci, vizualizaci a transformaci automatů konečného stavu a Turingových strojů, Jean Bovet
- JFLAP
- dk.brics.automaton
- libfa