Automatisk med magasinminne
I automatteorin är en pushdown- automat en finita tillståndsmaskin som använder en stack för att lagra tillstånd.
Formell definition
Till skillnad från vanliga finita automater är en pushdown-automat en uppsättning [1]
var
K är en ändlig uppsättning av automattillstånd, är det enda tillåtna initiala tillståndet för automaten, — uppsättning sluttillstånd och F=Ø och F=K är tillåtna, Σ är ett giltigt inmatningsalfabet från vilket strängar bildas som läses av automaten, S - minnes alfabet (butik), är ett nollminnestecken.
Minnet fungerar som en stack , det vill säga det sista elementet som skrivits till det är tillgängligt för läsning. Så övergångsfunktionen är en mappning . Det vill säga, baserat på kombinationen av det aktuella tillståndet, inmatningssymbolen och symbolen överst i butiken, väljer automaten nästa tillstånd och, möjligen, symbolen som ska skrivas till butiken. I fallet när finns i den högra delen av automatregeln läggs ingenting till i butiken och elementet från toppen raderas. Om butiken är tom utlöses reglerna c på vänster sida.
Klassen av språk som känns igen av push-down automater är densamma som klassen av sammanhangsfria språk .
I sin rena form används push-pull-automater sällan. Vanligtvis används denna modell för att visualisera skillnaden mellan vanliga finita automater och syntaktiska grammatiker . Implementeringen av pushdown-automater skiljer sig från finita automater genom att automatens nuvarande tillstånd starkt beror på någon tidigare.
Exempel med en pushdown-automat
upprepa X := top shop symbol ; om X = terminal eller $ så om X = InSym ta bort X från butiken ; InSym := nästa symbol ; else error () end else /* X = icke -terminal */ om M [ X , InSym ] = X -> Y1Y2 ... Yk radera sedan X från lagret ; lägg Yk , Yk - 1 , ... , Y1 i lager ( Y1 överst ) ; utdataregel X -> Y1Y2 ... Yk annat fel () /* tabellposten M är tom */ slutslut tills X = $ / * lagret är tomt * /Typer av push-pull-automater
Det finns deterministiska och icke- deterministiska pushdown- automater.
För icke-deterministiska automater (i motsats till deterministiska) finns det två likvärdiga termineringskriterier:
- tom butik,
- nå sluttillståndet.
En deterministisk automat avslutas först när den når sluttillståndet.
Se även
- JFLAP är en plattformsoberoende automatsimulator, Turing-maskin, grammatik, ritar en automatgraf.
Anteckningar
- ↑ Diskret matematik, 2006 , sid. 630.
Litteratur
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
- Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 sid. — ISBN 5-7038-2886-4 .
| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |