Batteridrevet automat

En batteridrevet automat er en abstrakt maskin som brukes i teoretisk informatikk og, mer presist, i automatteori .

En stablet automat er en generalisering av endelig automat  : den har også et uendelig minne organisert i en stack ( last-in / first-out eller LIFO ). En batteridrevet automat tar et ord som inngang og utfører en serie overganger. Det gjør en overgang for hver bokstav i ordet, avhengig av bokstaven, tilstanden til automaten og toppen av stabelen, og kan også endre innholdet i stabelen. Avhengig av tilstanden til PLC og batteriet på slutten av beregningen, godtas eller avvises ordet.

Språkene som aksepteres av batteridrevne automater er nøyaktig algebraiske språk , det vil si de som genereres av en algebraisk grammatikk .

Betydningen av pushdown automata kommer fra deres bruk i den syntaktiske analysen av programmeringsspråk , og mer generelt i transformasjonen av definisjoner eller rekursive algoritmer til deres iterative analoger.

Formell definisjon

Batteridrevet automat

En pushdown-automat (ikke-deterministisk) er en 7-tupel , der: PÅ=(Q,PÅ,Z,δ,z0,q0,T){\ displaystyle {\ mathcal {A}} = (Q, A, Z, \ delta, z_ {0}, q_ {0}, T)}

• Q{\ displaystyle Q}er settet med stater  ;
• PÅ{\ displaystyle A}er inngangsalfabetet  ;
• Z{\ displaystyle Z}er stabelalfabetet  ;
• δ:Q×(PÅ∪{ε})×Z→P(Q×Z∗){\ displaystyle \ delta: Q \ times (A \ cup \ {\ varepsilon \}) \ times Z \ rightarrow {\ mathcal {P}} (Q \ times Z ^ {*})}er overgangsfunksjonen (notasjonen betegner settet med deler );P{\ displaystyle {\ mathcal {P}}}
• z0∈ Z{\ displaystyle z_ {0} \ in \ Z}er bunnsymbolet  ;
• q0∈Q{\ displaystyle q_ {0} \ in Q}er den opprinnelige tilstanden  ;
• T⊂Q{\ displaystyle T \ subset Q}er settet med terminalstater .

I stedet for funksjonen møter vi ofte settet definert av δ{\ displaystyle \ delta}Δ⊂Q×(PÅ∪{ε})×Z×Q×Z∗{\ displaystyle \ Delta \ subset Q \ times (A \ cup \ {\ varepsilon \}) \ times Z \ times Q \ times Z ^ {*}}

(q,y,z,s,h)∈Δ⟺(s,h)∈δ(q,y,z){\ displaystyle (q, y, z, p, h) \ in \ Delta \ iff (p, h) \ in \ delta (q, y, z)}

Elementene i er reglene for overganger . Når vi snakker om en - regelen . Alle settene i definisjonen er endelige . Δ{\ displaystyle \ Delta}y=ε{\ displaystyle y = \ varepsilon}ε{\ displaystyle \ varepsilon}

En intern konfigurasjon av PLC er et par . En PLC- konfigurasjon er en triplett . En beregning av automaten på et ord er en serie overganger som starter fra den opprinnelige konfigurasjonen . Det er en overgang fra konfigurasjonen , hvor og til konfigurasjonen, og vi skriver: (q,h)∈Q×Z∗{\ displaystyle (q, h) \ i Q \ times Z ^ {*}}(q,w,h)∈Q×PÅ∗×Z∗{\ displaystyle (q, w, h) \ i Q \ times A ^ {*} \ times Z ^ {*}}w∈PÅ∗{\ displaystyle w \ i A ^ {*}} (q0,w,z0){\ displaystyle (q_ {0}, w, z_ {0})}(q,yw,zh){\ displaystyle (q, yw, zh)}y∈PÅ∪ε{\ displaystyle y \ i A \ cup {\ varepsilon}}z∈Z{\ displaystyle z \ in Z}(q′,w,h′h){\ displaystyle (q ', w, h'h)}

(q,yw,zh)⊢(q′,w,h′h){\ displaystyle (q, yw, zh) \ vdash (q ', w, h'h)}

når . Når endres ikke inntastingsordet. Vi snakker da om en - overgang eller en spontan overgang . I alle fall, for at en overgang skal være mulig, må ikke bunken være tom. (q′,h′)∈δ(q,y,z){\ displaystyle (q ', h') \ in \ delta (q, y, z)}y=ε{\ displaystyle y = \ varepsilon}ε{\ displaystyle \ varepsilon}

Vi sier at et ord aksepteres av automaten hvis det er en serie overganger som fører til en akseptabel konfigurasjon . Det finnes flere gjenkjennelsesmåter:

• Anerkjennelse med tomt batteri . De aksepterende konfigurasjonene er konfigurasjonene i skjemaet hvor det er en hvilken som helst tilstand. Det er med andre ord mulig å kunne tømme batteriet helt når du er ferdig med å lese ordet.(q,ε,ε){\ displaystyle (q, \ varepsilon, \ varepsilon)}q∈Q{\ displaystyle q \ i Q}
• Anerkjennelse etter sluttstatus . De aksepterende konfigurasjonene er konfigurasjonene i skjemaet hvor er en endelig tilstand. Bunken er derfor ikke nødvendigvis tom på slutten av ordlesingen.(t,ε,h){\ displaystyle (t, \ varepsilon, h)}t∈T{\ displaystyle t \ in T}
• Anerkjennelse ved tomt batteri og endelig tilstand . De aksepterende konfigurasjonene er konfigurasjonene i skjemaet hvor det er en endelig tilstand. Bunken er tom på slutten av ordlesingen.(t,ε,ε){\ displaystyle (t, \ varepsilon, \ varepsilon)}t∈T{\ displaystyle t \ in T}

Den språket anerkjent av automaton er sett av ord som er akseptert. PÅ{\ displaystyle {\ mathcal {A}}}PÅ∗{\ displaystyle A ^ {*}}

De tre aksepteringsmåtene er likeverdige, i den forstand at hvis et språk blir gjenkjent av en nedtrekksautomat av en art, kan vi bygge en automat som gjenkjenner dette språket, av andre arter.

Kommentarer

En batteridrevet automat består av to interagerende deler: automatdelen , med et endelig antall tilstander, og et uendelig hjelpeminne, organisert i en bunke. Vi forventer derfor å ha to operasjoner på bunken, en for å stable et symbol, en for å stakke en. Den matematiske definisjonen som er vedtatt, består i å erstatte disse to operasjonene med en enkelt som kombinerer dem, og som, i spesielle tilfeller, gir stabling og unstacking. Faktisk, hvis vi bruker en overgangsregel

(q,y,z,s,h){\ displaystyle (q, y, z, p, h)}

først stabler vi symbolet , så stabler vi ordet , så blir erstattet av . Hvis ordet er tomt, består operasjonen ganske enkelt av å stakke; hvis ordet begynner med , derfor hvis operasjonen tilsvarer å stable et annet ord oppå det . En tredje fordel med denne komprimerte notasjonen er at du kan teste karakteren til symbolet øverst i bunken, ganske enkelt ved å lese den og sette den tilbake. z{\ displaystyle z}h{\ displaystyle h}z{\ displaystyle z}h{\ displaystyle h}h{\ displaystyle h}h{\ displaystyle h}z{\ displaystyle z}h=zh′{\ displaystyle h = zh '}z{\ displaystyle z}h′{\ displaystyle h '}

I formalismen som presenteres, kan man ikke teste om bunken er tom, for hvis bunken er tom, er enhver beregning (som må starte med en unstacking) umulig. En måte å omgå denne vanskeligheten er å bruke et spesielt symbol nederst i bunken som du ikke fjerner.

Deterministisk stakeautomat

En push-down automat er deterministisk når overgangsfunksjonen er en delvis funksjon som tilfredsstiller en tilleggsbetingelse.

Mer presist, er en delvis funksjon . Videre, når er definert, er da ikke definert for noen bokstav . Dermed, hvis en spontan overgang er mulig, er ingen annen overgang mulig fra denne konfigurasjonen. δ{\ displaystyle \ delta}Q×(PÅ∪{ϵ})×Z→Q×Z∗{\ displaystyle Q \ times (A \ cup \ {\ epsilon \}) \ times Z \ rightarrow Q \ times Z ^ {*}}δ(q,ϵ,z){\ displaystyle \ delta (q, \ epsilon, z)}δ(q,på,z){\ displaystyle \ delta (q, a, z)}på∈PÅ{\ displaystyle a \ i A}

Gjenkjenningsmodusene, etter endelig tilstand eller med tomt batteri, er ikke lenger likeverdige. Et deterministisk algebraisk språk er et algebraisk språk som det er en endelig tilstands deterministisk push-down automat som gjenkjenner det. Deterministiske automater med tom stabelgjenkjenning gjenkjenner nøyaktig deterministiske algebraiske språk som er prefikser (intet ord i språket er et prefiks i et annet ord i språket).

For eksempel er språket prefiks, og gjenkjennes av de to typene deterministisk automat, men språket gjenkjennes bare av deterministisk automat av endelig tilstand. {påikkebikke∣ikke>0}{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n> 0 \}}på∗{\ displaystyle a ^ {*}}

Et eksempel

{påkbk∣k≥1}{\ displaystyle \ {a ^ {k} b ^ {k} \ mid k \ geq 1 \}}

Automaten har to tilstander  ; staten er innledende, det er ingen terminal tilstand. Anerkjennelse skjer ved tomt batteri . Bunnsymbolet er . Det er bare ett ekstra stack symbol, bemerket . Overgangene er: q,s{\ displaystyle q, p}q{\ displaystyle q}ω{\ displaystyle \ omega}PÅ{\ displaystyle A}

(q,på,ω,q,PÅ){\ displaystyle (q, a, \ omega, q, A)}

(q,på,PÅ,q,PÅPÅ){\ displaystyle (q, a, A, q, AA)}

(q,ε,PÅ,s,PÅ){\ displaystyle (q, \ varepsilon, A, p, A)}

(s,b,PÅ,s,ε){\ displaystyle (p, b, A, p, \ varepsilon)}

Den tredje regelen er en -regel. Hun sier at fra staten kan du gå til staten uten å lese noe, og uten å bytte batteri. ε{\ displaystyle \ varepsilon}q{\ displaystyle q}s{\ displaystyle p}

Vi starter med å lese det første tegnet:

• hvis ordet er tomt, er vi ferdige og ordet blir avvist fordi stabelen ikke er tom;
• hvis det er en , erstatter vi bunnen av bunken med  ;på{\ displaystyle a}PÅ{\ displaystyle A}
• hvis det er ett , avvises ordet fordi ingen regler gjelder.b{\ displaystyle b}

Så, ved hver lesing, stabler vi en ekstra etter regel (2). Etter å ha lest bokstaver etter hverandre, inneholder bunken . Hvis vi ser en mens den er i staten , henger maskinen fordi ingen regler gjelder. på{\ displaystyle a}PÅ{\ displaystyle A}k{\ displaystyle k}på{\ displaystyle a}PÅk{\ displaystyle A ^ {k}}b{\ displaystyle b}q{\ displaystyle q}

I tilstanden endres regel (3) til tilstand uten å lese et brev eller endre bunken. Da gjelder bare regel (4), og vi kan bruke den så lenge bunken ikke er tom, det vil si så mange ganger som vi har lest bokstaver . Aksept med tom stabel betyr at det innleste ordet aksepteres når bunken er tom, så når ordet har form . q{\ displaystyle q}s{\ displaystyle p}på{\ displaystyle a}påkbk{\ displaystyle a ^ {k} b ^ {k}}

Eksemplet ville være mer komplisert hvis vi ønsket å unngå -regelen. ε{\ displaystyle \ varepsilon}

Eiendommer

Hvert språk definert av en algebraisk grammatikk gjenkjennes av en pushdown-automat og omvendt.

Derfor er problemet med tilhørigheten av et ord til et algebraisk språk avgjørende  : det eksisterer en algoritme som, gitt beskrivelsen av en ikke-kontekstuell grammatikk og et ord, svarer på endelig tid på spørsmålet om medlemskapet av dette ordet i språk definert av denne grammatikken (mer presist, den kan testes på en gang for et ord med lengde n , takket være CYK-algoritmen ). O(ikke3){\ displaystyle O (n ^ {3})}

Klassen av rasjonelle språk (anerkjent av en endelig automat) er strengt tatt med i klassen av deterministiske algebraiske språk (anerkjent av en push-down automaton deterministisk av endelig tilstand), selv strengt tatt med i klassen av algebraiske språk (anerkjent av en push ned-automat). ikke deterministisk). For eksempel er språket deterministisk algebraisk, men ikke rasjonelt, og språket til palindromiske ord er algebraisk, men ikke deterministisk algebraisk. påikkebikke{\ displaystyle a ^ {n} b ^ {n}}

Begrensninger og utvidelser

Akseptmetoder

Andre variasjoner av aksept eksisterer. Dette er grunnen til at vi noen ganger møter en formulering som skiller definisjonen i to: på den ene siden defineres en stabelmaskin uten å spesifisere akseptmodusen. På den annen side er en automat spesifisert av dataene til de interne akseptkonfigurasjonene . For eksempel :

• settet beskriver aksept av tomt batteri;Q×{ε}{\ displaystyle Q \ times \ {\ varepsilon \}}
• settet beskriver aksept etter endelig tilstand;T×Z∗{\ displaystyle T \ times Z ^ {*}}
• settet beskriver aksept ved endelig tilstand og tom stabel.T×{ε}{\ displaystyle T \ times \ {\ varepsilon \}}

Sanntidsautomat

En pushdown-automat er i sanntid ( engelsk i sanntid ) hvis han ikke har -Rules. En batteridrevet automat er enkel hvis den bare har en tilstand. Vi kan vise at ethvert riktig algebraisk språk (dvs. ikke inneholder det tomme ordet) kan gjenkjennes av en enkel sanntids push-up-automat. ε{\ displaystyle \ varepsilon}

På den annen side kan ikke noe deterministisk språk gjenkjennes av en deterministisk push-down automat i sanntid. For eksempel språket

{påikkebsvs.påikke∣ikke,s>0}∪{påikkebsdbs∣ikke,s>0}{\ displaystyle \ {a ^ {n} b ^ {p} ca ^ {n} \ mid n, p> 0 \} \ cup \ {a ^ {n} b ^ {p} db ^ {p} \ mid n, p> 0 \}}

er deterministisk algebraisk, men kan ikke gjenkjennes av en deterministisk pushdown-automat i sanntid.

Stakk språk

Den stabel språket i en stablet automat er det sett av ord som vises på stabelen under en vellykket beregning, det vil si i en konfigurasjon av en rekke overganger fra den første konfigurasjon til en akseptere konfigurasjon. For en hvilken som helst push-down automat, og uansett hvilken akseptmodus, er stack- språket et rasjonelt språk . Karakteren til stablespråk - og mer generelt språket for mellomliggende memoriseringer - har blitt systematisk studert av Oscar H. Ibarra og IanMcQuillan.

To-stakk automat

En automat med to eller flere stabler har samme datakraft som en Turing-maskin . Faktisk er to-stakk-automata en generalisering av to-meters maskiner , som i seg selv tilsvarer Turing-maskiner. Det kan også demonstreres mer direkte: en automat med to stabler kan simulere en Turing-maskin ved å sørge for at delen av båndet til venstre for lesehodet blir registrert i den første stakken, og delen av båndet til høyre av spillhodet blir spilt inn på den andre.

Ekvivalensen av deterministisk pushdown-automat

Géraud Sénizergues beviste i 2001 at ekvivalensen til to deterministiske stakeautomater kan avgjøres. Dette problemet hadde vært åpent siden definisjonen av deterministisk automat på 1970-tallet. Géraud Sénizergues fikk Gödel-prisen for dette beviset.

applikasjoner

De fleste programmeringsspråk er beskrevet av en algebraisk grammatikk. Den syntaktiske analysen av et program, som er en av de første operasjonene som utføres av en kompilator , kan derfor utføres av en trykknappautomat. Hvis språkets grammatikk er en deterministisk algebraisk grammatikk, er det tilstrekkelig å konstruere en deterministisk push-down automat; Ellers må vi bygge en ikke-deterministisk push-down automat.

Det finnes automatiske verktøy for å bygge nedtrekksautomaten fra en beskrivelse av språkets grammatikk (for eksempel ANTLR ).

Implementering av en batteridrevet automat

Følgende kildeprogram i C-språk verifiserer at det angitte uttrykket respekterer språket i parentes der eventuell åpningsparentes må svare til en sluttparentes: