Státní automat

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. srpna 2022; kontroly vyžadují 6 úprav .

Konečný automat (KA) v teorii algoritmů je matematická abstrakce , model diskrétního zařízení , které má jeden vstup, jeden výstup a je v jednom stavu z mnoha možných v daném okamžiku. Jde o speciální případ abstraktního diskrétního automatu , jehož počet možných vnitřních stavů je konečný .

Během provozu jsou vstupní akce postupně přijímány na vstupu SC a na výstupu SC generuje výstupní signály. Obvykle pod vstupními vlivy je vstup automatu přijímán jako vstup symbolů jedné abecedy a výstup KA v procesu operace vydává symboly v obecném případě jiné, možná dokonce neprotínající se s vstup, abeceda.

Kromě konečných automatů existují také nekonečné diskrétní automaty - automaty s nekonečným počtem vnitřních stavů, například Turingův stroj .

Přechod z jednoho vnitřního stavu kosmické lodi do druhého může nastat nejen z vnějších vlivů, ale také spontánně.

Existují deterministické KA - automaty, u kterých je další stav jednoznačně určen aktuálním stavem a výstup závisí pouze na aktuálním stavu a aktuálním vstupu, a nedeterministické KA , jejichž další stav je obecně neurčitý a podle toho , výstupní signál není definován. Pokud k přechodu do následných stavů dochází s určitou pravděpodobností, pak se takový CA nazývá pravděpodobnostní CA.

Jakékoli digitální systémy, například počítače nebo některé logické uzly počítačů s paměťovými spouštěči a dalšími zařízeními , mohou sloužit jako příklady fyzické implementace KA . Kombinační sekvenční logika nemůže být CA, protože nemá žádné vnitřní stavy (nemá paměť).

Z abstraktního hlediska CA studuje sekci diskrétní matematiky - teorii konečných automatů .

Teorie konečných automatů je prakticky široce využívána např. v parserech a lexerech , modelovém testování softwaru .

Formální popis stavového automatu

Obecný formální popis

Formálně je CA definována jako uspořádaných pět prvků některých množin:

A=(S,X,Y,\delta ,\lambda),

kde je konečná množina stavů automatu;

S

X,Y

jsou konečné vstupní a výstupní abecedy, ze kterých jsou tvořeny řetězce, které automat čte a vydává;

\delta :S\krát X\šipka doprava S

- přechodová funkce;

\lambda :S\krát X\šipka doprava Y

je funkce výstupů.

Abstraktní automat s nějakým vybraným stavem (tento stav se nazývá počáteční stav ) se nazývá počáteční automat . Protože každý KA má konečný počet stavů a kterýkoli z jeho stavů lze přiřadit jako počáteční stav, odpovídá stejný automat počátečním automatům, tj. počtu vnitřních stavů KA. Abstraktní CA tedy definuje rodinu počátečních automatů. Pokud není zadán počáteční stav, pak je chování automatu vždy nedeterministické, výstupní slovo automatu závisí na počátečním stavu, takže úplný deterministický popis automatu bude [1] : ${\displaystyle s_{0))$ $N$ $N$

A=(S,X,Y,\delta ,\lambda ,s_{0}).

Existují dvě třídy KA: Mooreovy automaty - KA, ve kterých výstupní signál závisí pouze na vnitřním stavu, podle obrázku Mooreův automat nemá spojení mezi vstupem a výstupní funkcí , a Mealyho automaty - výstupní signál závisí jak na vnitřním stavu, tak na stavu vstupu. $x(t)$ $\lambda$

Obecný popis

Existují různé způsoby, jak specifikovat algoritmus pro fungování konečného automatu. Například konečný automat lze definovat jako uspořádaných pět prvků některých množin :

M=(V,Q,q_{0},F,\delta ),

kde je vstupní abeceda (konečná množina vstupních symbolů ), ze které jsou tvořena vstupní slova , vnímaná konečným automatem;

PROTI

Q

je množina vnitřních stavů ;

q_{0}

— výchozí stav ;

(q_{0}\v Q)

F

- soubor konečných nebo konečných stavů ;

(F\podmnožina Q)

\delta

je přechodová funkce definovaná jako takové zobrazení , že , tj. hodnota přechodové funkce na uspořádané dvojici (stav, vstupní symbol nebo prázdný řetězec symbolů) je množinou všech stavů, do kterých je možný přechod z daného stavu daný vstupní symbol nebo prázdný řetězec symbolů, obvykle označený písmenem

\delta \colon Q\times (V\cup \{\varepsilon \})\rightarrow Q

\delta (q,a)=\{r\dvojtečka q\,\,{\podmnožina {a}{\to }}\,\,r\}

\varepsilon.

Při analýze CA je obvyklé předpokládat, že konečný automat začíná v nějakém počátečním stavu , postupně přijímá jeden znak ze vstupního slova (řetězec vstupních znaků). Čtený znak může převést automat do nového stavu nebo nepřevést do nového stavu v souladu s přechodovou funkcí. $q_{0}$

Přijetí vstupního řetězce znaků a provádění přechodů ze stavu do stavu automat po obdržení posledního znaku $X$ [ upřesnit ] vstupní slovo bude v nějakém stavu . $q'$

Pokud je tento stav konečný, pak se říká, že automat slovo přijal $X$ [ vyčistit ]

Další způsoby nastavení fungování kosmické lodi

Výchozí stav	další stát
Výchozí stav	Vstupní znak a	Vstupní znak b	Jakákoli jiná postava
p0	p1	p0	p0
p1	p1	p2	p1
p2	p3	p4	p2
p3	p3	p5	p3
p4	p4	p4	p4
p5	p3	p5	p5

Stavový diagram (nebo někdy přechodový graf ) je grafické znázornění sady stavů a přechodové funkce. Je to označený orientovaný graf , jehož vrcholy jsou stavy KA, oblouky jsou přechody z jednoho stavu do druhého a štítky oblouků jsou symboly, kterými se provádí přechod z jednoho stavu do druhého. . Pokud lze přechod ze stavu q 1 do q 2 provést jedním z několika symbolů, pak musí být všechny označeny nad obloukem diagramu.
Tabulka přechodů je tabulkovou reprezentací funkce δ . Typicky v takové tabulce každý řádek odpovídá jednomu stavu a každý sloupec odpovídá jednomu platnému vstupnímu znaku. Buňka na průsečíku řádku a sloupce obsahuje stav, do kterého se musí automat dostat, pokud v tomto stavu přečte daný vstupní symbol. Příklad tabulky skoků pro automat uvedený jako graf na obrázku 1 je zobrazen vpravo.

Determinace

Stavové stroje se dělí na deterministické a nedeterministické .

Deterministický konečný automat (DFA) je takový automat, ve kterém nejsou žádné oblouky se štítkem ε (věta, která neobsahuje jediný symbol) a z jakéhokoli stavu pro jakýkoli symbol je přechod do nejvýše jednoho stavu. možný.
Nedeterministický konečný automat (NFA) je zobecněním deterministického automatu. Nedeterminismu automatů lze dosáhnout dvěma způsoby: buď mohou existovat přechody ze stavu do stavu způsobené prázdným řetězcem symbolů, tedy spontánní přechody bez vnějších vlivů, nebo může KA přejít z jednoho stavu do různých stavů. pod vlivem stejného symbolu.

Uvažujeme-li případ, kdy je automat formálně specifikován následovně: , kde je množina počátečních stavů automatu, taková, že , pak se objeví třetí znak nedeterminismu - přítomnost několika počátečních (počátečních) stavů pro automat . $M=(V,Q,S,F,\delta )$ $S$ $S\subseteq Q$ $M$

Určovací věta tvrdí, že pro jakýkoli konečný automat lze zkonstruovat ekvivalentní deterministický konečný automat (dva konečné automaty jsou považovány za ekvivalentní, pokud jsou jejich jazyky stejné[ jasné ] ). Protože však počet stavů v ekvivalentním DFA v nejhorším případě roste exponenciálně s růstem počtu stavů původního NFA, není v praxi takové určení vždy možné. Navíc jsou konečné automaty s výstupem obecně nedeterministické.

Vzhledem k posledním dvěma poznámkám se i přes větší složitost nedeterministických konečných automatů právě NFA používají především pro úlohy spojené se zpracováním textu. .

Automaty a běžné jazyky

Pro konečný automat je možné definovat v abecedě jazyk (množinu slov) , který umožňuje , tedy slova se nazývají, jejichž čtení převede automat z počátečního stavu do jednoho z koncových stavů. $PROTI$

Kleeneův teorém říká, že jazyk je regulární tehdy a jen tehdy, když je to povoleno nějakým stavovým automatem používaným v tomto jazyce.

Minimalizace automatů

Pro každý regulární jazyk existuje jedinečný, až do izomorfismu , automat, který tento jazyk přijímá a má nejmenší možný počet stavů. Minimální automat pro jazyk daný deterministickým konečným automatem lze implementovat v polynomiálním čase, což umožňuje optimalizovat spotřebu paměti potřebnou pro práci s automatem a také řešit problémy, jako je kontrola ekvivalence dvou automatů v polynomiálním čase. .

Specializované programovací jazyky

Sekvenční funkční diagram ( SFC ) je grafický programovací jazyk široce používaný pro programování průmyslových logických automatů ( PLC ).

V grafickém jazyce SFC je program popsán jako schematická posloupnost kroků spojených přechody.

Vývoj modelu pomocí konečných automatů

Konečné automaty umožňují vytvářet modely systémů paralelního zpracování, avšak pro změnu počtu paralelních procesů v takovém modelu je třeba provést významné změny v modelu samotném. Navíc pokus o vývoj komplexního modelu implementovaného konečným automatem vede k rychlému nárůstu počtu stavů automatu, což nakonec vývoj takového modelu extrémně zdlouhaví. Jak bylo uvedeno výše, druhý problém lze vyřešit použitím nedeterministického automatu.

Co umí konečný automat a sekvenční stroj?

Odpověď je dána různými termíny v závislosti na tom, zda je automat (respektive P-stroj) autonomní nebo ne [2] . Autonomní konečný automat, počínaje určitým cyklem, může generovat pouze periodickou sekvenci stavů x (respektive P-stroj je sekvence výstupních symbolů y ). Pokud se tato sekvence skládá pouze z jednoho symbolu, pak to znamená, že automat dosáhne rovnovážného stavu v konečném počtu cyklů. Pokud tato sekvence obsahuje několik symbolů, znamená to, že automat postupně prochází stavy odpovídajícími těmto symbolům a poté se činnost automatu periodicky opakuje donekonečna. Navíc, ať je periodická posloupnost stavů konečné délky jakákoli, vždy lze sestavit autonomní konečný automat, který počínaje druhým cyklem tuto posloupnost generuje. Nic jiného, kromě periodického opakování stejného stavu nebo konečné posloupnosti stavů, autonomní automat „nemůže“. Vzhledem k tomu, že sekvenční provádění daného cyklu operací je typické pro mnoho oblastí moderní techniky, jsou však široce využívány dynamické systémy, které lze v přijatelné idealizaci považovat za autonomní automat.

Klasickým příkladem jsou loutkové automaty, které provádějí složité sekvence akcí, například: psaní určitého textu na papír, hraní předem nastavených her na klavír atd.

Moderním příkladem jsou mnohé automaty, automatické linky a automatické řídicí systémy pro cyklickou výrobu. Pokud automat není autonomní, to znamená, že se stav vstupu mění cyklus od cyklu, pak odpověď na otázku, co může konečný automat „dělat“ a co nemůže „dělat“, může být podána různými termíny. Odpověď může být například formulována v jazyce reprezentace událostí. Neautonomní konečný automat nebo sekvenční stroj totiž pouze transformuje vstupní sekvence znaků na stavové nebo výstupní sekvence znaků a říci, co konečný automat může a nemůže „dělat“, znamená zjistit, které transformace sekvencí jsou možné v konečném automatu a které jsou nemožné. Ale protože počet stavů (respektive výstupních symbolů) je konečný, je tato otázka ekvivalentní následující otázce: v jakých vstupních sekvencích se vyskytuje každý z možných stavů (nebo každý z výstupních symbolů)? Tato poslední otázka, v pojmech akceptovaných v teorii konečných automatů, je formulována následovně: jaké události mohou a co nemohou být reprezentovány v konečném automatu každým z možných stavů (nebo každým z výstupních symbolů).

Odpověď je dána Kleeneovými teorémy . Tato odpověď je správná, protože Kleeneovy věty zakládají nezbytné a postačující podmínky pro reprezentovatelnost posloupnosti událostí v automatu, a to: rozlišují se speciální množiny posloupností vstupních symbolů - regulární množiny . Skutečnost, že se z takové množiny objeví vstupní sekvence, se nazývá odpovídající regulární událost. Kleeneovy teorémy stanoví, že v konečném automatu mohou být reprezentovány pouze pravidelné události. V jazyce reprezentace událostí je tedy odpověď na otázku, co konečný automat „dovede“, dána jednoznačně: konečný automat může reprezentovat pouze regulární události. Řada důležitých množin vstupních sekvencí, se kterými se člověk v praxi často musí vypořádat, je zjevně pravidelná. Je tedy známo, že například množina sestávající z libovolného konečného počtu vstupních sekvencí konečné délky je pravidelně pravidelná; soubor jakýchkoliv periodických vstupních sekvencí; sada nekonečných sekvencí, která obsahuje dané konečné sekvence za posledních několik cyklů atd.

V obecném případě, je-li nekonečná množina vstupních sekvencí dána nějakým libovolným způsobem, pak otázka, zda je tato množina regulární, zůstává otevřená. Jde o to, že pojem regulární množiny je zaveden induktivně, to znamená, že je stanoven algoritmus pro konstrukci jakýchkoli regulárních množin. Neexistuje však žádný dostatečně účinný způsob, jak vyřešit inverzní problém, tedy určit, zda je každá daná množina regulární.

Kleeneovy teorémy sice odpovídají na otázku, co dokáže stavový stroj, ale na tuto otázku odpovídají neefektivně. Byly učiněny první pokusy o konstrukci jiných jazyků, ve kterých lze efektivně odpovědět. Tento problém jazyka, který hraje zásadní roli při získávání efektivní odpovědi na otázku, co konečný automat může a nemůže „dělat“, je zásadní i pro první fáze syntézy automatů, tedy pro zodpovězení druhého z výše uvedené otázky. Pokud třídu dynamických systémů, kterou jsme definovali termíny „konečný automat“ a „sekvenční stroj“, rozšíříme o nekonečnou paměť (modelem nekonečné paměti může být např. nekonečná páska pro ukládání symbolů nebo např. nekonečný počet stavů), pak pro dynamické systémy této širší třídy (abstraktní systémy této třídy se nazývají Turingovy stroje ) odpověď na otázku "co dokážou?" mnohem jednodušší - mohou implementovat jakýkoli předdefinovaný algoritmus . Zároveň je samotný koncept algoritmu v moderní matematice interpretován jako implementace výpočtu hodnot jakékoli rekurzivní funkce . Tak jednoznačná a jasná odpověď na otázku "co umí Turingův stroj?" umožňuje založit pojem Turingova stroje jako základ pro definici pojmu algoritmus: algoritmus je jakýkoli proces, který lze provést na konečném automatu doplněném nekonečnou pamětí, tedy na algoritmicky úplných strojích, na Turingově stroji, na Postovém stroji atd.

Viz také

Mili stroj
Samopal Moore
JFLAP - multiplatformní simulátorový program (automaty, Turingovy stroje, gramatiky)
Automatické programování
Sekvenční funkční schéma
Kompilátor
Překladatel
Petriho sítě
Sekvenční logika (sekvenční logika)
Rozhodovací tabulka
Přípona automat

Poznámky

↑ Kuzněcov O. P., Adelson-Velsky G. M. Automata // Diskrétní matematika pro inženýra. - M .: Energie, 1980. - 344 s.
↑ Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Automaty. Algoritmy. Stát. vyd. Fyzikální matematika Literatura 1963, 556 stran.

Literatura

Belousov A. I., Tkachev S. B. Diskrétní matematika. - M. : MGTU, 2006. - S. 460-587. — ISBN 5-7038-2886-4 .
John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Diskrétní matematika. - 2. vyd. - Williams, 2002. - 528 s. - (Algoritmy a metody. Umění programování).
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
Teorie automatů / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Teorie pravděpodobnosti. Matematické statistiky. Teoretická kybernetika. - M.: VINITI, 1976. - T. 13. - S. 109-188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Využití konečných automatů pro řešení úloh automatizace
Glushkov V. M. Syntéza digitálních automatů. — M.: GIFML , 1962. — 476 s.

Odkazy

Dekhtyar M. I. Úvod do obvodů, automatů a algoritmů
Open source generátor konečných stavů v jazycích C++ a Java ze souborů s popisem XML
Nedeterministické stavové automaty
Podzorov S. Yu Kurz přednášek z teorie algoritmů

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus

V bibliografických katalozích	NKC : ph210246