I automatteorin är en pushdown- automat en finita tillståndsmaskin som använder en stack för att lagra tillstånd.
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.
Det finns deterministiska och icke- deterministiska pushdown- automater.
För icke-deterministiska automater (i motsats till deterministiska) finns det två likvärdiga termineringskriterier:
En deterministisk automat avslutas först när den når sluttillståndet.
Formella språk och formella grammatiker | |
---|---|
Allmänna begrepp | |
Typ 0 | |
Typ 1 |
|
Typ 2 | |
Typ 3 |
|
analysera |