Automatisk med magasinhukommelse
I automatteori er en pushdown- automat en finite state-maskine , der bruger en stak til at gemme tilstande.
Formel definition
I modsætning til almindelige finite automater er en pushdown-automat et sæt [1]
hvor
K er et endeligt sæt af automattilstande, er den eneste tilladte starttilstand for automaten, — sæt af sluttilstande, og F=Ø og F=K er tilladte, Σ er et gyldigt input-alfabet, hvorfra der dannes strenge, der læses af automaten, S - hukommelsens alfabet (butik), er et nulhukommelsestegn.
Hukommelse fungerer som en stak , det vil sige, at det sidste element, der er skrevet til den, er tilgængeligt til læsning. Så overgangsfunktionen er en kortlægning . Det vil sige, at baseret på kombinationen af den aktuelle tilstand, inputsymbolet og symbolet øverst i butikken, vælger automaten den næste tilstand og muligvis symbolet, der skal skrives til butikken. I tilfælde af, at når er til stede i den højre del af automatreglen , tilføjes intet til butikken, og elementet fra toppen slettes. Hvis butikken er tom, så udløses reglerne c i venstre side.
Klassen af sprog, der genkendes af push-down automater, er den samme som klassen af kontekstfri sprog .
I sin rene form bruges push-pull automater sjældent. Typisk bruges denne model til at visualisere forskellen mellem almindelige finite automater og syntaktiske grammatikker . Implementeringen af pushdown-automater adskiller sig fra endelige automater ved, at automatens nuværende tilstand afhænger stærkt af enhver tidligere.
Eksempel ved brug af en pushdown-automat
gentag X := top shop symbol ; hvis X = terminal eller $ , så hvis X = InSym , så fjern X fra butikken ; InSym := næste symbol ; else error () end else /* X = non -terminal */ hvis M [ X , InSym ] = X -> Y1Y2 ... Yk så slet X fra lageret ; læg Yk , Yk - 1 , ... , Y1 på lager ( Y1 øverst ) ; outputregel X -> Y1Y2 ... Yk anden fejl () /* tabelindtastning M er tom */ endeslut indtil X = $ / * lageret er tomt * /Typer af push-pull automater
Der er deterministiske og ikke -deterministiske pushdown- automater.
For ikke-deterministiske automater (i modsætning til deterministiske) er der to tilsvarende termineringskriterier:
- tom butik,
- når sluttilstanden.
En deterministisk automat ophører først, når den når den endelige tilstand.
Se også
- JFLAP er en cross-platform automat simulator, Turing maskine, grammatik, tegner en automat graf.
Noter
- ↑ Diskret matematik, 2006 , s. 630.
Litteratur
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
- Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |