Automat cu memorie revistă

În teoria automatelor , un automat pushdown este o mașină cu stări finite care folosește o stivă pentru a stoca stări.

Definiție formală

Spre deosebire de automatele finite obișnuite, un automat pushdown este un set [1]

M=(K,\Sigma,\pi,s,F,S,e),

Unde

K este un set finit de stări automate,

s\în K

este singura stare inițială permisă a automatului,

F\subseteq K

— un set de stări finale și F=Ø și F=K sunt admisibile, Σ este un alfabet de intrare valid din care se formează șiruri care sunt citite de automat, S - alfabetul memoriei (magazin),

e\în S

este un caracter de memorie nul.

Memoria funcționează ca o stivă , adică ultimul element scris în ea este disponibil pentru citire. Deci funcția de tranziție este o mapare . Adică, pe baza combinației dintre starea curentă, simbolul de intrare și simbolul din partea de sus a magazinului, automatul selectează următoarea stare și, eventual, simbolul de scris în magazin. În cazul în care este prezent în partea dreaptă a regulii automate , nu se adaugă nimic în magazin, iar elementul din partea de sus este șters. Dacă magazinul este gol, atunci se declanșează regulile c din partea stângă. $\pi :K\times \Sigma \times S\la K\times S$ $e$ $e$

Clasa de limbi recunoscute de automatele push-down este aceeași cu clasa de limbi fără context .

În forma sa pură, automatele push-pull sunt rar folosite. De obicei, acest model este folosit pentru a vizualiza diferența dintre automatele finite obișnuite și gramaticile sintactice . Implementarea automatelor pushdown diferă de automatele finite prin faptul că starea actuală a automatului depinde puternic de oricare dintre cele anterioare.

Exemplu de utilizare a unui automat pushdown

repeta X := simbolul magazinului de top ; dacă X = terminal sau $ atunci dacă X = InSym atunci eliminați X din magazin ; InSym := simbolul următor ; else error () end else /* X = non -terminal */ if M [ X , InSym ] = X -> Y1Y2 ... Yk atunci șterge X din magazin ; pune Yk , Yk - 1 , ... , Y1 în magazin ( Y1 deasupra ) ; regula de ieșire X -> Y1Y2 ... Yk else error () /* intrarea tabelului M este goală */ sfârșitul sfârșitului până când X = $ /* magazinul este gol */

Tipuri de automate push-pull

Există automate pushdown deterministe și nedeterministe .

Pentru automatele nedeterministe (spre deosebire de cele deterministe), există două criterii de terminare echivalente:

magazin gol,
ajungând la starea finală.

Un automat determinist se termină numai când ajunge în starea finală.

Vezi și

JFLAP este un simulator de automată multiplatformă, mașină Turing, gramatică, desenează un grafic automat.

Note

↑ Matematică discretă, 2006 , p. 630.

Literatură

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Matematică discretă. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami