Statsmaskin

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 augusti 2022; kontroller kräver 6 redigeringar .

En finit automat (KA) i teorin om algoritmer är en matematisk abstraktion , en modell av en diskret enhet som har en ingång, en utgång och är i ett tillstånd av många möjliga vid varje given tidpunkt. Det är ett specialfall av en abstrakt diskret automat , vars antal möjliga interna tillstånd är ändligt .

Under drift mottas ingångsåtgärderna sekventiellt vid ingången till SC, och vid utgången genererar SC utgångssignaler. Vanligtvis, under ingångspåverkan, accepteras inmatningen av automaten som ingången av symboler för ett alfabet , och utmatningen av KA i driftprocessen ger ut symboler i det allmänna fallet med en annan, kanske till och med inte korsar den ingång, alfabet.

Förutom finita automater finns det också oändliga diskreta automater - automater med ett oändligt antal interna tillstånd, till exempel en Turing-maskin .

Övergången från ett inre tillstånd av rymdfarkosten till ett annat kan ske inte bara från yttre påverkan, utan också spontant.

Det finns deterministiska KA - automater, där nästa tillstånd unikt bestäms av det aktuella tillståndet och utsignalen endast beror på det aktuella tillståndet och den aktuella ingången, och icke- deterministiska KA , vars nästa tillstånd i allmänhet är obestämd och följaktligen , är utsignalen inte definierad. Om övergången till efterföljande tillstånd sker med vissa sannolikheter, kallas en sådan CA en probabilistisk CA.

Alla digitala system, till exempel datorer eller några logiska noder av datorer med minnestriggers och andra enheter , kan fungera som exempel på den fysiska implementeringen av KA . Den kombinerade sekventiella logiken kan inte vara en CA, eftersom den inte har några interna tillstånd (den har inget minne).

Ur en abstrakt synvinkel studerar CA ett avsnitt av diskret matematik - teorin om finita automater .

Teorin om finita automater används praktiskt taget flitigt, till exempel i parsers och lexers , modellbaserad mjukvarutestning .

Formell beskrivning av tillståndsmaskinen

Allmän formell beskrivning

Formellt definieras CA som fem ordnade element i vissa uppsättningar:

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

där är en ändlig uppsättning av automattillstånd;

S

X,Y

är de slutliga in- respektive utgående alfabeten, från vilka strängar bildas som läses och matas ut av automaten;

\delta :S\ gånger X\högerpil S

- övergångsfunktion;

\lambda :S\ gånger X\högerpil Y

är utgångarnas funktion.

En abstrakt automat med något valt tillstånd (detta tillstånd kallas initialtillstånd ) kallas initialautomat . Eftersom varje KA har ett ändligt antal tillstånd, och vilket som helst av dess tillstånd kan tilldelas som ett initialt tillstånd, motsvarar samma automat till initiala automater, dvs antalet interna tillstånd för KA. Således definierar en abstrakt CA en familj av initiala automater. Om det initiala tillståndet inte är specificerat, är automatens beteende alltid icke-deterministiskt, automatens utgångsord beror på initialtillståndet, så den fullständiga deterministiska beskrivningen av automaten kommer att vara [1] : ${\displaystyle s_{0))$ $N$ $N$

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

Det finns två klasser av KA: Moore automata - KA, där utsignalen endast beror på det interna tillståndet, enligt figuren har Moore-automaten ingen anslutning från ingången till utgångsfunktionen och Mealy automata - utsignalen beror på både det interna tillståndet och tillståndet för ingången. $x(t)$ $\lambda$

Allmän beskrivning

Det finns olika sätt att specificera algoritmen för funktionen hos en finit automat. Till exempel kan en finit automat definieras som fem ordnade element i vissa uppsättningar :

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

var är inmatningsalfabetet (en ändlig uppsättning ingångssymboler ), från vilken inmatningsorden bildas , uppfattat av den finita automaten;

V

F

är uppsättningen av interna tillstånd ;

q_{0}

— initialtillstånd ;

(q_{0}\in Q)

F

- en uppsättning slut- eller sluttillstånd ;

(F\subset Q)

\delta

är en övergångsfunktion definierad som en mappning så att , det vill säga värdet av övergångsfunktionen på ett ordnat par (tillstånd, ingångssymbol eller tom sträng av symboler) är uppsättningen av alla tillstånd till vilka en övergång från ett givet tillstånd är möjlig för en given inmatningssymbol eller tom sträng av symboler, vanligtvis betecknad med bokstaven

\delta \colon Q\times (V\cup \{\varepsilon \})\högerpil Q

\delta (q,a)=\{r\kolon q\,\,{\underset {a}{\to }}\,\,r\}

\varepsilon.

När man analyserar CA är det vanligt att anta att den finita automaten startar i något initialt tillstånd , sekventiellt tar emot ett tecken från inmatningsordet (en kedja av indatatecken). Lästecknet kan överföra automaten till ett nytt tillstånd eller inte överföra till ett nytt tillstånd i enlighet med övergångsfunktionen. $q_{0}$

Att ta emot en inmatningssträng av tecken och göra övergångar från tillstånd till tillstånd, automaten efter att ha tagit emot det sista tecknet $x$ [ förtydliga ] inmatningsordet kommer att vara i något tillstånd . $q'$

Om detta tillstånd är slutgiltigt, sägs automaten ha accepterat ordet $x$ [ klara upp ]

Andra sätt att ställa in rymdfarkostens funktion

Initialt tillstånd	nästa stat
Initialt tillstånd	Mata in tecken a	Inmatningssymbol b	Vilken annan karaktär som helst
p0	p1	p0	p0
p1	p1	p2	p1
p2	p3	p4	p2
p3	p3	p5	p3
p4	p4	p4	p4
p5	p3	p5	p5

Ett tillståndsdiagram (eller ibland en övergångsgraf ) är en grafisk representation av en uppsättning tillstånd och en övergångsfunktion. Det är en märkt riktad graf , vars hörn är KA:s tillstånd, bågarna är övergångarna från ett tillstånd till ett annat, och bågarnas etiketter är symbolerna med vilka övergången från ett tillstånd till ett annat utförs . Om övergången från tillståndet q 1 till q 2 kan utföras av en av flera symboler, måste alla av dem märkas ovanför diagrammets båge.
Övergångstabellen är en tabellrepresentation av funktionen δ . Typiskt, i en sådan tabell, motsvarar varje rad ett tillstånd och varje kolumn motsvarar ett giltigt inmatningstecken. Cellen i skärningspunkten mellan raden och kolumnen innehåller det tillstånd som automaten måste gå in i om den läser den givna inmatningssymbolen i detta tillstånd. Ett exempel på en hopptabell för en automat ges som en graf i figur 1 visas till höger.

Beslutsamhet

Statsmaskiner är indelade i deterministiska och icke- deterministiska .

En deterministisk finit automat (DFA) är en sådan automat där det inte finns några bågar med etiketten ε (en mening som inte innehåller en enda symbol), och från vilket tillstånd som helst för någon symbol är en övergång till inte mer än ett tillstånd möjlig.
En icke-deterministisk finit automat (NFA) är en generalisering av en deterministisk. Automaternas icke-determinism kan uppnås på två sätt: antingen kan det finnas övergångar från tillstånd till tillstånd orsakade av en tom kedja av symboler, det vill säga spontana övergångar utan yttre påverkan, eller så kan en KA gå från ett tillstånd till olika tillstånd under påverkan av samma symbol.

Om vi betraktar fallet när automaten är formellt specificerad enligt följande: , där är uppsättningen av initialtillstånd för automaten, så att , då det tredje tecknet på nondeterminism visas - närvaron av flera initiala (start)tillstånd för automaten . $M=(V,Q,S,F,\delta )$ $S$ $S\subseteq Q$ $M$

Bestämningssats hävdar att för varje finita tillståndsmaskin kan en ekvivalent deterministisk finita tillståndsmaskin konstrueras (två finita tillståndsmaskiner sägs vara likvärdiga om deras språk är samma[ rensa ] ). Men eftersom antalet tillstånd i den ekvivalenta DFA i värsta fall växer exponentiellt med ökningen av antalet tillstånd i den ursprungliga NFA, är en sådan bestämning i praktiken inte alltid möjlig. Dessutom är ändliga automater med utgång i allmänhet indeterministiska.

På grund av de två sista anmärkningarna, trots den större komplexiteten hos icke-deterministiska finita automater, är det NFA:er som huvudsakligen används för uppgifter relaterade till textbehandling. .

Automater och vanliga språk

För en finit automat är det möjligt att definiera ett språk (en uppsättning ord) i alfabetet som den tillåter , dvs orden kallas, vars läsning överför automaten från initialtillståndet till ett av sluttillstånden. $V$

Kleenes teorem säger att ett språk är regelbundet om och endast om det tillåts av någon tillståndsmaskin som används i det språket.

Minimering av automater

För alla vanliga språk finns det en unik, upp till isomorfism , automat som accepterar detta språk och har minsta möjliga antal tillstånd. Minimiautomaten för ett språk som ges av en deterministisk finit automat kan implementeras i polynomtid, vilket gör att du kan optimera minnesförbrukningen som krävs för att arbeta med automaten, samt lösa problem som att kontrollera ekvivalensen av två automater i polynomtid .

Specialiserade programmeringsspråk

Sequential Function Chart ( SFC ) är ett grafiskt programmeringsspråk som ofta används för programmering av industriella logiska styrenheter ( PLC ).

I det grafiska språket SFC beskrivs ett program som en schematisk sekvens av steg sammankopplade genom övergångar.

Modellutveckling med finita tillståndsmaskiner

Finita automater låter dig bygga modeller av parallella bearbetningssystem, men för att ändra antalet parallella processer i en sådan modell måste du göra betydande ändringar i själva modellen. Dessutom leder ett försök att utveckla en komplex modell implementerad av en finit automat till en snabb ökning av antalet tillstånd hos automaten, vilket så småningom kommer att göra utvecklingen av en sådan modell extremt tidskrävande. Som noterats ovan kan det senare problemet lösas genom att använda en icke-deterministisk automat.

Vad kan en finita tillståndsmaskin och en sekventiell maskin "göra"?

Svaret ges i olika termer beroende på om automaten (respektive P-maskinen) är autonom eller inte [2] . En autonom finit automat, utgående från en viss cykel, kan endast generera en periodisk sekvens av tillstånd x (en P-maskin är en sekvens av utgående symboler y ). Om denna sekvens endast består av en symbol betyder det att automaten når ett jämviktstillstånd i ett ändligt antal cykler. Om denna sekvens innehåller flera symboler, betyder detta att automaten successivt passerar genom tillstånden som motsvarar dessa symboler, och sedan upprepas automatens operation periodvis i oändlighet. Dessutom, oavsett den periodiska sekvensen av tillstånd av ändlig längd, kan en autonom ändlig automat alltid byggas, som, med början från den andra cykeln, genererar denna sekvens. Ingenting annat, förutom den periodiska upprepningen av samma tillstånd eller en ändlig sekvens av tillstånd, kan den autonoma automaten "göra". Men på grund av det faktum att sekventiell exekvering av en given cykel av operationer är typisk för många områden av modern teknik, används dynamiska system, som i en acceptabel idealisering, kan betraktas som en autonom automat, i stor utsträckning.

Ett klassiskt exempel är dockautomater som utför komplexa sekvenser av åtgärder, till exempel: skriva en viss text på papper, spela förinställda pjäser på pianot, etc.

Ett modernt exempel är många automatiska maskiner, automatiska linjer och automatiska styrsystem för cyklisk produktion. Om automaten inte är autonom, det vill säga ingångens tillstånd ändras från cykel till cykel, kan svaret på frågan om vad en finit automat kan "göra" och vad som inte kan "göra" ges i olika termer. Till exempel kan svaret formuleras i ett händelserepresentationsspråk. I själva verket omvandlar en icke-autonom finit automat eller sekventiell maskin bara indatateckensekvenser till tillstånds- eller utdatateckensekvenser, och att säga vad en finit automat kan och inte kan "göra" är att ta reda på vilka sekvenstransformationer som är möjliga i en finit automat och som är omöjliga. Men eftersom antalet tillstånd (respektive utmatningssymboler) är ändligt, motsvarar denna fråga följande fråga: vid vilka ingångssekvenser inträffar vart och ett av de möjliga tillstånden (eller var och en av de utgående symbolerna)? Denna sista fråga, i termer som accepteras i teorin om finita automater, är formulerad enligt följande: vilka händelser kan och vad som inte kan representeras i en finit automat av vart och ett av de möjliga tillstånden (eller av var och en av de utgående symbolerna).

Svaret ges av Kleenes satser . Detta svar är korrekt, eftersom Kleenes satser fastställer nödvändiga och tillräckliga villkor för representabiliteten av en händelsesekvens i en automat, nämligen: speciella uppsättningar av sekvenser av ingångssymboler särskiljs - regelbundna uppsättningar . Det faktum att en inmatningssekvens uppträder från en sådan uppsättning kallas den motsvarande vanliga händelsen. Kleenes satser slår fast att endast regelbundna händelser kan representeras i en finit automat. Sålunda, i händelserepresentationens språk, ges svaret på frågan om vad en finit automat kan "göra" entydigt: en finit automat kan bara representera regelbundna händelser. Ett antal viktiga uppsättningar av ingångssekvenser, som man ofta måste hantera i praktiken, är uppenbarligen regelbundna. Så, till exempel, är en uppsättning som består av ett ändligt antal ingångssekvenser av ändlig längd känt för att vara regelbundet regelbundet; uppsättningen av eventuella periodiska inmatningssekvenser; en uppsättning oändliga sekvenser som innehåller givna ändliga sekvenser under de senaste cyklerna, etc.

I det allmänna fallet, om en oändlig uppsättning ingångssekvenser ges på något godtyckligt sätt, förblir frågan om denna uppsättning är regelbunden öppen. Poängen är att begreppet en vanlig mängd introduceras induktivt, det vill säga en algoritm för att konstruera eventuella reguljära mängder etableras. Det finns dock inget tillräckligt effektivt sätt att lösa det omvända problemet, det vill säga att avgöra om varje given mängd är regelbunden.

Även om Kleenes teorem svarar på frågan om vad en statsmaskin kan göra, svarar de på denna fråga ineffektivt. De första försöken har gjorts för att konstruera andra språk där svaret kan ges effektivt. Detta språkproblem, som spelar en kardinal roll för att få ett effektivt svar på frågan om vad en finit automat kan och inte kan "göra", är också avgörande för de första stegen av automatsyntesen, det vill säga för att svara på det andra av ovanstående frågor. Om vi utökar klassen av dynamiska system, som vi har definierat med termerna "ändlig automat" och "sekventiell maskin", genom att inkludera oändligt minne (modellen av oändligt minne kan till exempel vara ett oändligt band för att lagra symboler eller en oändligt antal tillstånd), då för dynamiska system av denna bredare klass (abstrakta system av denna klass kallas Turing-maskiner ) svaret på frågan "vad kan de göra?" mycket enklare - de kan implementera vilken fördefinierad algoritm som helst . Samtidigt tolkas själva begreppet en algoritm i modern matematik som en implementering av att beräkna värdena för alla rekursiva funktioner . Ett så entydigt och tydligt svar på frågan "vad kan en Turing-maskin göra?" gör det möjligt att lägga begreppet Turingmaskin som grund för definitionen av begreppet en algoritm: en algoritm är vilken process som helst som kan utföras på en finit automat kompletterad med oändligt minne, det vill säga algoritmiskt kompletta maskiner, på en Turingmaskin, på en Postmaskin osv.

Se även

Mili maskin
Moore kulspruta
JFLAP - plattformsoberoende simulatorprogram (automater, Turing-maskiner, grammatik)
Automatisk programmering
Sekventiella funktionsdiagram
Kompilator
Översättare
Petri nät
Sekventiell logik (sekventiell logik)
Beslutstabell
Suffix automat

Anteckningar

↑ Kuznetsov O. P., Adelson-Velsky G. M. Automata // Diskret matematik för en ingenjör. - M . : Energi, 1980. - 344 sid.
↑ Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Automata. Algoritmer. Stat. ed. Phys.-Matte. Litteratur 1963, 556 sidor.

Litteratur

Belousov A. I., Tkachev S. B. Diskret matematik. - M. : MGTU, 2006. - S. 460-587. — ISBN 5-7038-2886-4 .
John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Diskret matematik. - 2:a uppl. - Williams, 2002. - 528 sid. - (Algorithms and methods. Konsten att programmera).
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori och implementering av programmeringsspråk - M.: MZ-Press, 2006, 2nd ed. — ISBN 5-94073-094-9
Automatateory / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Sannolikhetsteori. Matematik statistik. Teoretisk kybernetik. - 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
Användningen av finita automater för att lösa automationsproblem
Glushkov V. M. Syntes av digitala automater. — M.: GIFML , 1962. — 476 sid.

Länkar

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm

I bibliografiska kataloger	NKC : ph210246