Deterministisk tilstandsmaskine

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 24. juni 2022; checks kræver 3 redigeringer .

En deterministisk endelig automat ( DFA , DFA , eng. deterministic finite automaton , DFSA , eng. deterministic finite-state automaton , DFSM eng. deterministic finite-state machine ), også kendt som en deterministisk finite-genkendelse , er en finit automat , der accepterer eller afviser en given streng karakterer ved at passere gennem sekvensen af tilstande defineret af strengen [1] . Har en enkelt sekvens af tilstande under drift. McCulloch og Walter Pitts var blandt de første forskere, der foreslog et statsmaskine-lignende koncept i 1943 [2] [3] .

Figuren illustrerer en deterministisk finite state-maskine ved hjælp af et tilstandsdiagram . I dette eksempel er der tre tilstande - S 0 , S 1 og S 2 (afspejlet i figuren af cirkler). Automaten accepterer en endelig række af nuller og ettaller som input. For hver tilstand er der en overgangspil, der fører fra tilstand til tilstand for både 0 og 1. Efter at have læst et symbol, går DFA deterministisk fra en tilstand til en anden, efter overgangspilen. Hvis f.eks. automaten er i tilstand S0, og indgangssymbolet er 1, så går automaten deterministisk over til tilstand S1 . En DFA har en begyndelsestilstand (grafisk repræsenteret af en ud af ingenting-pil), hvorfra beregningen starter, og et sæt endelige tilstande (grafisk repræsenteret som en dobbelt cirkel), der bestemmer, om beregningen lykkes.

DFA er defineret som et abstrakt matematisk begreb, men implementeres ofte i hardware og software for at løse specifikke problemer. For eksempel kan en DFA modellere programmer, der afgør, om en brugerindtastet e - mailadresse er gyldig.

DFA genkender præcis en række regulære sprog [1] , der blandt andet er nyttige til leksikalsk analyse og mønstermatchning . DFA'er kan bygges ud fra nondeterministic finite automata ( NFA'er ) ved at reducere DFA'er til NFA'er .

Formel definition

En deterministisk finit automat er en 5 -tupel bestående af $M$ $(Q,\Sigma,\delta,q_{0},F)$

endeligt sæt af tilstande $Q$
et begrænset sæt af inputtegn, kaldet alfabetet $\Sigma$
overgangsfunktion _ $\delta :Q\ gange \Sigma \rightarrow Q$
begyndelsestilstand $q_{0}\in Q$
sæt af sluttilstande $F\subseteq Q$

Lad være en snor over alfabetet . Automaten accepterer en streng, hvis tilstandssekvensen eksisterer i med følgende betingelser ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $M$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $Q$

$r_{0}=q_{0}$
$r_{i+1}=\delta (r_{i},a_{i+1})$ , til $i=0,...,n-1$
$r_{n}\in F$ .

Med andre ord siger den første betingelse, at maskinen starter fra staten . Den anden betingelse siger, at for en given strengkarakter går maskinen over fra tilstand til tilstand i henhold til overgangsfunktionen . Den sidste betingelse siger, at maskinen accepterer, hvis strengens sidste inputtegn får maskinen til at gå til en af de endelige tilstande. Ellers siges automaten at afvise strengen. Det sæt af strenge, der accepterer, er et sprog , der genkendes af automaten , og dette sprog er betegnet med . $q_{0}$ $w$ $\delta$ $w$ $w$ $M$ $M$ $L(M)$

En deterministisk endelig tilstandsmaskine uden sluttilstande og ingen starttilstand er kendt som et overgangssystem eller semiautomaton .

For en mere komplet formel definition, se artiklen " Automata Theory ".

Fuldstændige og ufuldstændige automater

Ifølge ovenstående definition er deterministiske endelige automater altid komplette - de definerer en overgang for hver tilstand og for hvert inputsymbol.

Mens den anvendte definition er den mest almindeligt accepterede, bruger nogle forfattere udtrykket deterministisk endelig automat om et lidt anderledes koncept - en automat, der højst definerer én overgang (i stedet for præcis én som i ovenstående definition) for hver tilstand og hvert inputsymbol . Overgangsfunktionen er tilladt at være delvist defineret . Hvis overgangen ikke er defineret, stopper maskinen.

Eksempel

Følgende eksempel er en binær DFA, der kræver, at inputtet indeholder et lige antal nuller. $M$

$M=(Q,\Sigma,\delta,q_{0},F)$ hvor

$Q=\{S_{1},S_{2}\}$
$\Sigma =\{0,1\}$
${\displaystyle q_{0}=S_{1))$
$F=\{S_{1}\}$ og
$\delta$ defineret af følgende springtabel :

	0	en
S1 _	S2 _	S1 _
S2 _	S1 _	S2 _

Sluttilstanden svarer til et lige antal nuller i inputstrengen, mens den taler om et ulige tal. 1 i inputstrømmen ændrer ikke automatens tilstand. Når inputstrengen slutter, vil den endelige tilstand indikere, om inputstrengen indeholdt et lige antal nuller eller ej. Hvis inputstrengen indeholder et lige antal nuller, vil den ende i den endelige tilstand , så inputstrengen vil blive accepteret. $S_{1}$ $S_{2}$ $M$ $S_{1}$

Det sprog, der genkendes, er et regulært sprog defineret af et regulært udtryk , hvor er en Kleene-stjerne , hvilket for eksempel betyder et hvilket som helst tal (muligvis nul) af på hinanden følgende 1'ere. $M$ ((1*) 0 (1*) 0 (1*))**1*

Lukningsegenskaber

Hvis DFA genkender sprog, der opnås ved at anvende en operation på sprog, der er anerkendt af DFA, siges DFA at være lukket under operationen. DFA'er er lukket under følgende handlinger.

En forening
Kryds [4] (se figur)
Sammenkædning
Tilføjelse
Kleene lukning
Appel
Gentagelse
Forskel
Substitution
Homomorfi

For hver operation bestemmes den optimale konstruktion, under hensyntagen til antallet af tilstande, i studiet af positionskompleksitet .

Fordi DFA'er svarer til nondeterministic finite automata (NFA'er ) , kan disse lukninger bevises ved hjælp af NFA-lukningsegenskaber.

Som en monoid af overgange

Driften af en given DFA kan ses som en sekvens af superpositioner af en meget generel formulering af overgangsfunktioner på sig selv. Vi vil bygge sådan en funktion her.

For et givet inputsymbol kan du konstruere en overgangsfunktion ved at definere for alle . (Denne teknik kaldes currying .) I dette perspektiv "virker" på Q-tilstanden for at producere en anden tilstand. Man kan overveje resultatet af en superposition af funktioner , successivt anvendt på forskellige funktioner , og så videre. Givet et par bogstaver , kan man definere en ny funktion , hvor betegner en superposition af funktioner. $a\in\Sigma$ $\delta _{a}:Q\rightarrow Q$ $\delta _{a}(q)=\delta (q,a)$ $q\in Q$ $\delta _{a}$ $\delta _{a}$ ${\displaystyle \delta _{b))$ $a,b\in \Sigma$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ $\cirk$

Det er klart, at denne proces kan fortsættes rekursivt, hvilket giver følgende rekursive definition : ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$

{\widehat {\delta }}(q,\epsilon )=q

, hvor er den tomme streng, og

\epsilon

{\widehat {\delta }}(q,wa)=\delta ({\widehat {\delta }}(q,w),a)

, hvor og .

w\in \Sigma ^{*},a\in \Sigma

q\in Q

Funktionen er defineret for alle ord . DFA's arbejde er en sekvens af superpositioner på sig selv. ${\widehat {\delta ))$ $w\in \Sigma ^{*}$ ${\widehat {\delta ))$

Gentagelsen af superpositioner af funktioner danner en monoid . For overgangsfunktioner er denne monoid kendt som overgangsmonoiden , eller nogle gange som transformationshalvgruppen . Konstruktionen kan vendes - hvis den er givet , kan man rekonstruere , så de to beskrivelser er ækvivalente. ${\widehat {\delta ))$ $\delta$

Lokale automater

En lokal automat er en DFA, hvor alle buer med den samme etiket fører til det samme toppunkt. Lokale automater accepterer klassen af formelle sprog , for hvilke et ords tilhørsforhold til et sprog bestemmes af et "glidende vindue" med længden to på ordet [5] [6]

Myhill-grafen over alfabetet A er en rettet graf med toppunktsæt A og en delmængde af toppunkter mærket "initial" og "terminal". Sproget, der accepteres af Myhill-grafen, er sættet af dirigerede stier fra startspidsen til slutspidsen - grafen fungerer så som en automat [5] . Klassen af sprog, der opfattes af Myhill-grafer, er klassen af lokale sprog [7] .

Stokastik i DFA

Når starttilstanden og sluttilstanden ignoreres, kan en DFA med tilstande og et størrelsesalfabet opfattes som en vertex -digraf , hvor alle toppunkter har mærket udgående buer (outcome-digraph ). Det er kendt, at når er et fast heltal, med stor sandsynlighed er den største stærkt forbundne komponent ( SCC), hvor digrafen med udfald er valgt ensartet tilfældigt, har en lineær størrelse og kan nås fra ethvert toppunkt [8] . Det blev også bevist, at når , stiger som , har hele digrafen en faseovergang til en stærk forbindelse, svarende til Erdős-Rényi-modellen for tilslutning [9] . $n$ $k$ $n$ $k$ $1,\ldots ,k$ $k$ $k\geqslant 2$ $k$ $k$ $n$

I en tilfældig DFA er det maksimale antal toppunkter, der kan nås fra ét toppunkt med høj sandsynlighed, meget tæt på antallet af toppunkter i den største stærkt forbundne komponent [8] [10] . Dette gælder også for den største genererede undergraf med minimum en i grader, som kan opfattes som en rettet version af -kernen [9] . $en$

Fordele og ulemper

DFA er en af de mest praktiske beregningsmodeller, da der er en triviel onlinealgoritme lineær tid og konstant hukommelse til simulering af DFA på inputstrømmen. Der er også effektive søgealgoritmer til DFA-genkendelse:

færdiggørelse af det sprog, der er anerkendt af den givne DFA.
union/skæringspunkt mellem sprog, der er anerkendt af to givne DFA'er.

Fordi DFA'er kan reduceres til en kanonisk form ( minimale DFA'er ), er der også to effektive algoritmer til at bestemme

om DFA accepterer en streng (tom testopgave)
om DFA accepterer alle rækker (universitetstestproblem)
om to DFA'er accepterer det samme sprog (Equivalence Testing Problem)
om et sprog, der er genkendt af en DFA, er indeholdt i et sprog, der er anerkendt af en anden DFA (Inclusion Check Task)
DFA med et minimum antal tilstande for et bestemt almindeligt sprog (minimeringsproblem)

DFA'er er beregningsmæssigt ækvivalente med ikke- deterministiske endelige automater (NFA'er, ikke- deterministiske endelige automater , NFA'er). Dette skyldes for det første, at enhver DFA også er en NFA, så en NFA kan gøre alt, hvad en DFA kan. Også givet en NFA kan man ved at reducere en DFA til en NFA konstruere en DFA, der genkender det samme sprog som NFA, selvom en DFA kan have eksponentielt flere tilstande end en NFA [11] [12] . Men selvom NFA'er er beregningsmæssigt ækvivalente med DFA'er, løses ovenstående problemer ikke nødvendigvis effektivt for NFA'er. Ikke-universalitetsproblemet for en NFA har PSPACE -kompleksitet , da der er små NFA'er med de mindste eksponentielle ord, der skal afvises. En DFA er universel, hvis og kun hvis alle tilstande er endelige, men dette er ikke sandt for en NFA. Ækvivalens-, inklusion- og minimeringsproblemerne har også PSPACE- kompleksitet , da de kræver dannelsen af komplementet af NFA, hvilket fører til en eksponentiel størrelseseksplosion [13] .

På den anden side er statsmaskiner stærkt begrænset på de sprog, de genkender. Mange simple sprog, inklusive ethvert problem, der kræver mere end konstant hukommelse at løse, kan ikke genkendes af DFA. Et klassisk eksempel på et simpelt sprog, som ingen DFA kan genkende, er parenteser eller Dyck-sprog , det vil sige et sprog, der består af korrekt adskilte parenteser, som i ordet "(()())". Det er intuitivt klart, at ingen DFA kan genkende Dycks sprog, da DFA'er ikke kan lave beregninger - automater som DFA'er har brug for en tilstand, der repræsenterer et hvilket som helst muligt antal "åbne" parenteser, hvilket betyder, at de skal have et ubegrænset antal tilstande. Et andet simpelt eksempel er et sprog, der består af strenge af formen for et begrænset, men vilkårligt stort antal bogstaver a efterfulgt af lige mange bogstaver b [14] . ${\displaystyle a^{n}b^{n))$

Se også

Deterministisk acyklisk endelig automat
DFA minimering
Monadisk logik af anden orden
Reduktion af NFA til DFA
Quantum state machine
Turing-maskiner med læsehoved, der bevæger sig til højre
Ordadskillelsesproblem
Turing maskine
To-vejs deterministisk endelig maskine

Noter

↑ 1 2 Hopcroft, Motwani, Ullman, 2001 .
↑ McCulloch, Pitts, 1943 .
↑ Rabin, Scott, 1959 .
↑ Hopcroft, Ullman, 1979 , s. 59-60.
↑ 12 Lawson , 2004 , s. 129.
↑ Sakarovitch, 2009 , s. 228.
↑ Lawson, 2004 , s. 128.
↑ 1 2 Grusho, 1973 , s. 633-637.
↑ 1 2 Cai, Devroye, 2017 , s. 428-458.
↑ Carayol, Nicaud, 2012 , s. 194-205.
↑ Sakarovitch, 2009 , s. 105.
↑ Lawson, 2004 , s. 63.
↑ Startseite - Lehrstuhl für Theoretische Informatik . Hentet 6. februar 2020. Arkiveret fra originalen 8. august 2018. (ubestemt)
↑ Lawson, 2004 , s. 46.

Litteratur

John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introduktion til automatteori, sprog og beregning . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
Mark V. Lawson. Endelig automatisk. - Chapman og Hall/CRC, 2004. - ISBN 1-58488-255-7 .
McCulloch W.S., Pitts W. A Logical Calculus of the Ideas Immanent in Nervous Activity // Bulletin of Mathematical Biophysics. - 1943. - V. 5 , no. 4 . — S. 115–133 . - doi : 10.1007/BF02478259 . Arkiveret fra originalen den 12. april 2019.
Rabin MO, Scott D. Finite automata og deres beslutningsproblemer. // IBM J. Res. dev. - 1959. - T. 3 , udg. 2 . — S. 114–125 . - doi : 10.1147/rd.32.0114 .
Jacques Sakarovitch. Elements of automatateory / Oversat fra fransk af Reuben Thomas. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Michael Sipser. Introduktion til teorien om beregning . - Boston: PWS, 1997. - ISBN 0-534-94728-X . Afsnit 1.1: Finite Automata, pp. 31-47. Underafsnit "Afgørlige problemer vedrørende almindelige sprog" i afsnit 4.1: Afgørlige sprog, s. 152-155.4.4 DFA kan kun acceptere almindeligt sprog
John E. Hopcroft, Jeffrey D. Ullman. Introduktion til automatteori, sprog og beregning . - Læsning/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- Oversat af John Hopcroft, Rajiv Motwani, Geoffrey Ullman. Introduktion til teorien om automater, sprog og beregninger. - Moskva, St. Petersborg, Kiev: Williams, 2002. - ISBN 5-8459-0261-4 .
Grusho A. A. Om grænsefordelingerne af nogle karakteristika ved tilfældige automatgrafer // Matem. noter. - 1973. - T. 4 . - S. 133-141, 633-637. - doi : 10.1007/BF01095785 .
Xing Shi Cai, Luc Devroye. Grafstrukturen af en deterministisk automat valgt tilfældigt // Random Structures & Algorithms. - 2017. - Oktober ( bind 51 , hæfte 3 ). - doi : 10.1002/rsa.20707 .
Arnaud Carayol, Cyril Nicaud. Fordeling af antallet af tilgængelige tilstande i en tilfældig deterministisk automat // STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) . - Paris, Frankrig, 2012. - T. 14.

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