Statsmaskine

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. august 2022; checks kræver 6 redigeringer .

En endelig automat (KA) i teorien om algoritmer er en matematisk abstraktion , en model af en diskret enhed , der har én indgang, én udgang og er i én tilstand ud af mange mulige på et givet tidspunkt. Det er et særligt tilfælde af en abstrakt diskret automat , hvor antallet af mulige interne tilstande er begrænset .

Under drift modtages inputhandlingerne sekventielt ved indgangen af SC, og ved udgangen genererer SC udgangssignaler. Normalt, under inputpåvirkninger, accepteres automatens input som input af symboler i et alfabet , og outputtet af KA i driftsprocessen udsender symboler i det generelle tilfælde af en anden, måske endda ikke skærende med input, alfabet.

Udover endelige automater findes der også uendelige diskrete automater - automater med et uendeligt antal interne tilstande, for eksempel en Turing-maskine .

Overgangen fra en indre tilstand af rumfartøjet til en anden kan ske ikke kun fra ydre påvirkninger, men også spontant.

Der er deterministiske KA - automater, hvor den næste tilstand er entydigt bestemt af den aktuelle tilstand, og outputtet kun afhænger af den aktuelle tilstand og det aktuelle input, og ikke- deterministiske KA , hvis næste tilstand generelt er ubestemt og følgelig , udgangssignalet er ikke defineret. Hvis overgangen til efterfølgende tilstande sker med visse sandsynligheder, kaldes en sådan CA en probabilistisk CA.

Alle digitale systemer, for eksempel computere eller nogle logiske noder af computere med hukommelsestriggere og andre enheder , kan tjene som eksempler på den fysiske implementering af KA . Den sekventielle kombinationslogik kan ikke være en CA, da den ikke har nogen interne tilstande (den har ingen hukommelse).

Fra et abstrakt synspunkt studerer CA et afsnit af diskret matematik - teorien om endelige automater .

Teorien om endelige automater er praktisk talt brugt, for eksempel i parsere og lexere , modelbaseret softwaretestning .

Formel beskrivelse af statsmaskinen

Generel formel beskrivelse

Formelt er CA defineret som en ordnet fem elementer i nogle sæt:

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

hvor er et endeligt sæt af automattilstande;

S

X,Y

er henholdsvis de endelige input- og output-alfabeter, hvorfra der dannes strenge, der læses og udlæses af automaten;

\delta :S\ gange X\højrepil S

- overgangsfunktion;

\lambda :S\ gange X\højrepil Y

er udgangenes funktion.

En abstrakt automat med en eller anden valgt tilstand (denne tilstand kaldes initial tilstand ) kaldes initial automat . Da hver KA har et endeligt antal tilstande, og enhver af dens tilstande kan tildeles som en begyndelsestilstand, svarer den samme automat til initialautomater, dvs. antallet af interne tilstande i KA'en. En abstrakt CA definerer således en familie af initiale automater. Hvis starttilstanden ikke er specificeret, så er opførselen af automaten altid ikke-deterministisk, automatens outputord afhænger af starttilstanden, så den komplette deterministiske beskrivelse af automaten vil være [1] : ${\displaystyle s_{0))$ $N$ $N$

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

Der er to klasser af KA: Moore automata - KA, hvor udgangssignalet kun afhænger af den interne tilstand, ifølge figuren har Moore automaten ingen forbindelse fra input til udgangsfunktionen , og Mealy automata - udgangssignalet afhænger af både den interne tilstand og tilstanden af input. $x(t)$ $\lambda$

Generel beskrivelse

Der er forskellige måder at specificere algoritmen for funktionen af en endelig automat. For eksempel kan en endelig automat defineres som et ordnede fem elementer i nogle sæt :

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

hvor er input-alfabetet (et endeligt sæt af inputsymboler ), hvorfra inputordene er dannet , opfattet af den endelige automat;

V

Q

er sættet af interne tilstande ;

q_{0}

— begyndelsestilstand ;

(q_{0}\i Q)

F

- et sæt slut- eller sluttilstande ;

(F\undersæt Q)

\delta

er en overgangsfunktion defineret som en mapping således , at værdien af overgangsfunktionen på et ordnet par (tilstand, inputsymbol eller tom streng af symboler) er sættet af alle tilstande, hvortil en overgang fra en given tilstand er mulig for et givet inputsymbol eller tom streng af symboler, normalt angivet med bogstavet

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

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

\varepsilon.

Når man analyserer CA, er det sædvanligt at antage, at den endelige automat starter i en eller anden initial tilstand , sekventielt modtager et tegn fra inputordet (en kæde af inputtegn). Det læste tegn kan overføre automaten til en ny tilstand eller ikke overføre til en ny tilstand i overensstemmelse med overgangsfunktionen. $q_{0}$

Modtagelse af en inputstreng af tegn og foretage overgange fra tilstand til tilstand, automaten efter at have modtaget det sidste tegn $x$ [ klargør ] inputordet vil være i en eller anden tilstand . $q'$

Hvis denne tilstand er endelig, siges automaten at have accepteret ordet $x$ [ ryd op ]

Andre måder at indstille rumfartøjets funktion på

Oprindelig tilstand	næste stat
Oprindelig tilstand	Indtast tegn a	Indtast tegn b	Enhver anden karakter
p0	p1	p0	p0
p1	p1	s2	p1
s2	s3	s4	s2
s3	s3	p5	s3
s4	s4	s4	s4
p5	s3	p5	p5

Et tilstandsdiagram (eller nogle gange en overgangsgraf ) er en grafisk repræsentation af et sæt tilstande og en overgangsfunktion. Det er en mærket rettet graf , hvis toppunkter er KA's tilstande, buerne er overgangene fra en tilstand til en anden, og buernes etiketter er de symboler, hvormed overgangen fra en tilstand til en anden udføres. . Hvis overgangen fra tilstanden q 1 til q 2 kan udføres af et af flere symboler, skal de alle være mærket over diagrammets bue.
Overgangstabellen er en tabelrepræsentation af funktionen δ . I en sådan tabel svarer hver række typisk til én tilstand, og hver kolonne svarer til ét gyldigt inputtegn. Cellen i skæringspunktet mellem rækken og kolonnen indeholder den tilstand, som automaten skal gå i, hvis den læser det givne inputsymbol i denne tilstand. Et eksempel på en springtabel for en automat givet som en graf i figur 1 er vist til højre.

Bestemmelse

Statsmaskiner er opdelt i deterministiske og ikke- deterministiske .

En deterministisk endelig automat (DFA) er en sådan automat, hvor der ikke er nogen buer med etiketten ε (en sætning, der ikke indeholder et enkelt symbol), og fra en hvilken som helst tilstand for ethvert symbol er en overgang til ikke mere end én tilstand muligt.
En ikke-deterministisk finit automat (NFA) er en generalisering af en deterministisk. Automaternes ikke-determinisme kan opnås på to måder: enten kan der være overgange fra tilstand til tilstand forårsaget af en tom kæde af symboler, det vil sige spontane overgange uden ydre påvirkninger, eller en KA kan gå fra en tilstand til forskellige tilstande under påvirkning af det samme symbol.

Hvis vi betragter tilfældet, når automaten formelt er specificeret som følger: , hvor er sættet af initialtilstande af automaten, sådan at , Så vises det tredje tegn på nondeterminisme - tilstedeværelsen af flere initiale (start)tilstande for automaten . $M=(V,Q,S,F,\delta )$ $S$ $S\subseteq Q$ $M$

Bestemmelsessætning hævder, at for enhver finite state-maskine kan en ækvivalent deterministisk finite state-maskine konstrueres (to finite state-maskiner siges at være ækvivalente, hvis deres sprog er de samme[ slet ] ). Men da antallet af stater i den tilsvarende DFA i værste fald vokser eksponentielt med væksten i antallet af stater i den oprindelige NFA, er en sådan bestemmelse i praksis ikke altid mulig. Derudover er endelige automater med output generelt indeterministiske.

På grund af de sidste to bemærkninger, på trods af den større kompleksitet af ikke-deterministiske endelige automater, er det NFA'er, der hovedsageligt bruges til opgaver relateret til tekstbehandling. .

Automater og almindelige sprog

For en finit automat er det muligt at definere et sprog (et sæt ord) i alfabetet , som det tillader , dvs. ordene kaldes, hvis læsning overfører automaten fra starttilstanden til en af sluttilstandene. $V$

Kleenes teorem siger, at et sprog er regulært , hvis og kun hvis det er tilladt af en eller anden statsmaskine, der bruges i det sprog.

Minimering af automater

For ethvert almindeligt sprog er der en unik, op til isomorfisme , automat, der accepterer dette sprog og har det mindst mulige antal tilstande. Minimumsautomaten for et sprog givet af en deterministisk finit automat kan implementeres i polynomiel tid, hvilket giver dig mulighed for at optimere det hukommelsesforbrug, der kræves for at arbejde med automaten, samt løse problemer såsom at kontrollere ækvivalensen af to automater i polynomisk tid .

Specialiserede programmeringssprog

Sequential Function Chart ( SFC ) er et grafisk programmeringssprog, der er meget udbredt til programmering af industrielle logiske controllere ( PLC'er ).

I det grafiske sprog SFC beskrives et program som en skematisk sekvens af trin forbundet med overgange.

Modeludvikling ved hjælp af finite state-maskiner

Finite automater giver dig mulighed for at bygge modeller af parallelle behandlingssystemer, men for at ændre antallet af parallelle processer i en sådan model, skal du foretage væsentlige ændringer i selve modellen. Derudover fører et forsøg på at udvikle en kompleks model implementeret af en endelig automat til en hurtig stigning i antallet af automatens tilstande, hvilket i sidste ende vil gøre udviklingen af en sådan model ekstremt tidskrævende. Som nævnt ovenfor kan sidstnævnte problem løses ved at bruge en ikke-deterministisk automat.

Hvad kan en finite state-maskine og en sekventiel maskine "gøre"?

Svaret gives i forskellige termer alt efter om automaten (henholdsvis P-maskinen) er autonom eller ej [2] . En autonom finit automat, startende fra en bestemt cyklus, kan kun generere en periodisk sekvens af tilstande x (henholdsvis en P-maskine er en sekvens af outputsymboler y ). Hvis denne sekvens kun består af et symbol, betyder det, at automaten når en ligevægtstilstand i et begrænset antal cyklusser. Hvis denne sekvens indeholder flere symboler, betyder det, at automaten successivt passerer gennem de tilstande, der svarer til disse symboler, og derefter gentages automatens drift periodisk i det uendelige. Desuden, uanset den periodiske sekvens af tilstande af begrænset længde, kan der altid bygges en autonom, endelig automat, som, startende fra den anden cyklus, genererer denne sekvens. Intet andet, bortset fra den periodiske gentagelse af den samme tilstand eller en endelig række af tilstande, kan den autonome automat "gøre". Men på grund af det faktum, at den sekventielle udførelse af en given cyklus af operationer er typisk for mange områder af moderne teknologi, er dynamiske systemer, som i en acceptabel idealisering kan betragtes som en autonom automat, meget brugt.

Et klassisk eksempel er dukkeautomater, der udfører komplekse sekvenser af handlinger, for eksempel: at skrive en bestemt tekst på papir, spille forudindstillede spil på klaveret osv.

Et moderne eksempel er mange automatiske maskiner, automatiske linjer og automatiske styresystemer til cyklisk produktion. Hvis automaten ikke er autonom, det vil sige, at inputtilstanden ændrer sig fra cyklus til cyklus, så kan svaret på spørgsmålet om, hvad en endelig automat kan "gøre", og hvad ikke kan "gøre", gives i forskellige termer. For eksempel kan svaret formuleres i et hændelsesrepræsentationssprog. Faktisk transformerer en ikke-autonom endelig automat eller sekventiel maskine kun input-tegnsekvenser til tilstands- eller output-tegnsekvenser, og at sige, hvad en finit automaton kan og ikke kan "gøre", er at finde ud af, hvilke sekvenstransformationer der er mulige i en endelig automat og som er umulige. Men da antallet af tilstande (henholdsvis outputsymboler) er begrænset, svarer dette spørgsmål til følgende spørgsmål: Ved hvilke inputsekvenser forekommer hver af de mulige tilstande (eller hvert af outputsymbolerne)? Dette sidste spørgsmål, i termer, der accepteres i teorien om endelige automater, er formuleret som følger: hvilke hændelser kan og hvad kan ikke repræsenteres i den endelige automat ved hver af de mulige tilstande (eller af hvert af outputsymbolerne).

Svaret er givet af Kleenes sætninger . Dette svar er korrekt, da Kleenes sætninger etablerer nødvendige og tilstrækkelige betingelser for repræsentativiteten af en sekvens af begivenheder i en automat, nemlig: særlige sæt af sekvenser af inputsymboler skelnes - regulære sæt . Det faktum, at en inputsekvens optræder fra et sådant sæt, kaldes den tilsvarende regulære hændelse. Kleenes sætninger fastslår, at kun regulære begivenheder kan repræsenteres i en endelig automat. I hændelsesrepræsentationens sprog er svaret på spørgsmålet om, hvad en finit automat kan "gøre" således entydigt givet: en finit automat kan kun repræsentere regulære begivenheder. En række vigtige sæt inputsekvenser, som man ofte skal forholde sig til i praksis, er åbenbart regulære. Så for eksempel er et sæt bestående af et vilkårligt begrænset antal inputsekvenser af endelig længde kendt for at være regelmæssigt regelmæssigt; sættet af eventuelle periodiske inputsekvenser; et sæt af uendelige sekvenser, der indeholder givne endelige sekvenser over de sidste par cyklusser osv.

I det generelle tilfælde, hvis et uendeligt sæt af inputsekvenser er givet på en eller anden vilkårlig måde, så forbliver spørgsmålet om, hvorvidt dette sæt er regulært, åbent. Pointen er, at begrebet et regulært sæt introduceres induktivt, det vil sige, at der etableres en algoritme til at konstruere ethvert regulært sæt. Der er dog ingen tilstrækkelig effektiv måde at løse det omvendte problem på, det vil sige at afgøre, om hvert givet sæt er regulært.

Selvom Kleenes teoremer besvarer spørgsmålet om, hvad en statsmaskine kan gøre, svarer de på dette spørgsmål ineffektivt. De første forsøg er blevet gjort på at konstruere andre sprog, hvor svaret kan gives effektivt. Dette sprogproblem, som spiller en kardinal rolle i at opnå et effektivt svar på spørgsmålet om, hvad en endelig automat kan og ikke kan "gøre", er også afgørende for de første stadier af automatsyntese, dvs. for at besvare den anden af ovenstående spørgsmål. Hvis vi udvider klassen af dynamiske systemer, som vi har defineret ved begreberne "endelig automat" og "sekventiel maskine", ved at inkludere uendelig hukommelse (modellen af uendelig hukommelse kan f.eks. være et uendeligt bånd til lagring af symboler eller en uendeligt antal tilstande), så for dynamiske systemer af denne bredere klasse (abstrakte systemer af denne klasse kaldes Turing-maskiner ) svaret på spørgsmålet "hvad kan de gøre?" meget enklere - de kan implementere enhver foruddefineret algoritme . Samtidig fortolkes selve begrebet en algoritme i moderne matematik som en implementering af beregning af værdierne af enhver rekursiv funktion . Sådan et entydigt og klart svar på spørgsmålet "hvad kan en Turing-maskine?" gør det muligt at sætte begrebet Turing-maskine som grundlag for definitionen af begrebet en algoritme: en algoritme er enhver proces, der kan udføres på en endelig automat suppleret med uendelig hukommelse, det vil sige algoritmisk komplette maskiner, på en Turing-maskine, på en Post-maskine osv.

Se også

Mili maskine
Moore maskinpistol
JFLAP - simulatorprogram på tværs af platforme (automater, Turing-maskiner, grammatikker)
Automatisk programmering
Sekventielt funktionsdiagram
Kompiler
Oversætter
Petri net
Sekventiel logik (sekventiel logik)
Beslutningstabel
Suffiks automat

Noter

↑ Kuznetsov O. P., Adelson-Velsky G. M. Automata // Diskret matematik for en ingeniør. - M . : Energi, 1980. - 344 s.
↑ Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Automata. Algoritmer. Stat. udg. Fysisk.-Matematik. Litteratur 1963, 556 sider.

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. udg. - Williams, 2002. - 528 s. - (Algorithmer og metoder. Kunsten at programmere).
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori og implementering af programmeringssprog - M.: MZ-Press, 2006, 2. udg. — ISBN 5-94073-094-9
Automateteori / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Sandsynlighedsteori. 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
Brugen af endelige automater til løsning af automatiseringsproblemer
Glushkov V. M. Syntese af digitale automater. — M.: GIFML , 1962. — 476 s.

Links

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme

I bibliografiske kataloger	NKC : ph210246