Automat cu baterie

Un automat stivuit sau (cunoscut și sub acronimul PDA , din engleza pushdown automaton ) este un tip de mașină abstractă , în special un automat a cărui memorie de lucru este alcătuită dintr-un teanc , o structură de date ale cărei date pot fi extrase în mod necesar invers ordin cu privire la cea de inserare. Un automat stivuit este capabil să recunoască și să accepte toate limbajele care în teoria gramaticilor formale sunt numite non-contextuale sau de tip 2 conform clasificării ierarhice a lui Chomsky .

Definiție formală

Automat nedeterminist stivuit

Automatul stivei nedeterministe este un sistem formal compus din $M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )$ ${\ displaystyle M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)}$ $M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)$ ^[1] , unde:

$\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este alfabetul introdus;
$\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamă$ este alfabetul simbolurilor grămezii;
$Z_{0}\in \Gamma$ ${\ displaystyle Z_ {0} \ in \ Gamma}$ $Z_ {0} \ in \ Gamma$ este caracterul de pornire al stivei;
$Î$ ${\ displaystyle Q}$ $Î$ este un set finit și ne-gol de stări;
$q_{0}\in Q$ ${\ displaystyle q_ {0} \ în Q}$ $q_ {0} \ în Q$ este starea inițială;
$F\subseteq Q$ ${\ displaystyle F \ subseteq Q}$ $F \ subseteq Q$ este ansamblul stărilor finale;
$\delta :Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \to {\mathcal {P}}_{finite}(Q\times \Gamma ^{\star })$ ${\ displaystyle \ delta: Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma \ to {\ mathcal {P}} _ {finite} (Q \ times \ Gamma ^ {\ star}) }$ $\ delta: Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma \ to {\ mathcal {P}} _ {{finite}} (Q \ times \ Gamma ^ {\ star})$ este funcția de tranziție parțială ( $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ este șirul gol).

Automat de stivă determinist

Un automat determinist acționat pe baterie este un automat acționat pe baterie $M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )$ ${\ displaystyle M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)}$ $M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)$ astfel încât pentru orice personaj o di $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ , pentru fiecare stat $Z$ ${\ displaystyle Z}$ $Z$ din $\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamă$ și pentru fiecare stat $q$ ${\ displaystyle q}$ $q$ din $Î$ ${\ displaystyle Q}$ $Î$ da ai $|\delta (q,a,Z)|+|\delta (q,\varepsilon ,Z)|<2$ ${\ displaystyle | \ delta (q, a, Z) | + | \ delta (q, \ varepsilon, Z) | <2}$ $| \ delta (q, a, Z) | + | \ delta (q, \ varepsilon, Z) | <2$

Configurarea unui automat cu baterie

Având un automat acționat de baterie $M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )$ ${\ displaystyle M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)}$ $M = (\ Sigma, \ Gamma, Z_ {0}, Q, q_ {0}, F, \ delta)$ se numește configurație a $M.$ ${\ displaystyle M}$ $M.$ un triplu $(q,x,\gamma )$ ${\ displaystyle (q, x, \ gamma)}$ $(q, x, \ gamma)$ , unde este $q$ ${\ displaystyle q}$ $q$ aparține lui $Î$ ${\ displaystyle Q}$ $Î$ , $X$ ${\ displaystyle x}$ $X$ la $\Sigma ^{\star }$ ${\ displaystyle \ Sigma ^ {\ star}}$ $\ Sigma ^ {\ star}$ Și $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ la $\Gamma ^{\star }$ ${\ displaystyle \ Gamma ^ {\ star}}$ $\ Gamma ^ {\ star}$ .

Acceptarea automatelor cu baterii

Un automat stivuit are două moduri diferite de a accepta o limbă:

Acceptare pentru stiva goală

Având un automat acționat de baterie $M.$ ${\ displaystyle M}$ $M.$ , una dintre configurațiile sale este acceptarea dacă $x=\gamma =\varepsilon$ ${\ displaystyle x = \ gamma = \ varepsilon}$ $x = \ gamma = \ varepsilon$ . Pe baza acestei definiții, un șir $X$ ${\ displaystyle x}$ $X$ este acceptat de un automat cu baterie dacă și numai dacă la sfârșitul procesării $X$ ${\ displaystyle x}$ $X$ stiva este goală.

Acceptarea statutului final

Exemplu

Să vedem acum exemplul unui automat determinist alimentat de baterie, care recunoaște limbajul $\{0^{n}1^{n}\mid n\geq 0\}$ ${\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}$ ${\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}$ pentru statutul final:

PDA pentru

\{0^{n}1^{n}\mid n\geq 0\}

{\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}

\ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}

(pentru statutul final)

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$ ${\ displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ Z, \ F)}$ ${\ displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ Z, \ F)}$ , cu

alfabet de intrare: $\Sigma =\{0,1\}$ ${\ displaystyle \ Sigma = \ {0,1 \}}$ ${\ displaystyle \ Sigma = \ {0,1 \}}$
alfabetul simbolului stivei: $\Gamma =\{A,Z\}$ ${\ displaystyle \ Gamma = \ {A, Z \}}$ ${\ displaystyle \ Gamma = \ {A, Z \}}$
caracterul de pornire al stivei: $Z\in \Gamma$ ${\ displaystyle Z \ in \ Gamma}$ ${\ displaystyle Z \ in \ Gamma}$
Statele: $Q=\{p,q,r\}$ ${\ displaystyle Q = \ {p, q, r \}}$ ${\ displaystyle Q = \ {p, q, r \}}$
stare initiala: $q_{0}=p$ ${\ displaystyle q_ {0} = p}$ ${\ displaystyle q_ {0} = p}$
stări finale: $F=\{r\}$ ${\ displaystyle F = \ {r \}}$ ${\ displaystyle F = \ {r \}}$
funcție de tranziție ( $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ este șirul gol) - format din următoarele 6 instrucțiuni:

(p,0,Z,p,AZ)

{\ displaystyle (p, 0, Z, p, AZ)}

{\ displaystyle (p, 0, Z, p, AZ)}

,

(p,0,A,p,AA)

{\ displaystyle (p, 0, A, p, AA)}

{\ displaystyle (p, 0, A, p, AA)}

,

(p,\epsilon ,Z,q,Z)

{\ displaystyle (p, \ epsilon, Z, q, Z)}

{\ displaystyle (p, \ epsilon, Z, q, Z)}

,

(p,\epsilon ,A,q,A)

{\ displaystyle (p, \ epsilon, A, q, A)}

{\ displaystyle (p, \ epsilon, A, q, A)}

,

(q,1,A,q,\epsilon )

{\ displaystyle (q, 1, A, q, \ epsilon)}

{\ displaystyle (q, 1, A, q, \ epsilon)}

,

(q,\epsilon ,Z,r,Z)

{\ displaystyle (q, \ epsilon, Z, r, Z)}

{\ displaystyle (q, \ epsilon, Z, r, Z)}

.

Primele două afirmații spun că într-o stare p , pentru fiecare citire 0 , A se adaugă la stivă. Adăugarea unui A peste un alt A este formalizată prin scrierea AA (la fel cum AZ simbolizează introducerea unui A peste un Z ). A treia și a patra afirmație indică o tranziție epsilon (adică o tranziție nedeterministă, care poate avea loc în orice moment) de la starea p la starea q . A cincea afirmație spune că într-o stare q , pentru fiecare 1 pat, un A este scos din partea de sus a stivei. În cele din urmă, a șasea instrucțiune spune că mașina trece de la starea q la starea finală r numai atunci când stiva este alcătuită doar din variabila Z (adică variabila inițial pe stivă). Aceasta înseamnă că automatul acceptă numai cuvinte în care numărul de 0 este echilibrat cu numărul următoarelor 1 .

Având un automat acționat de baterie $M.$ ${\ displaystyle M}$ $M.$ , una dintre configurațiile sale $(q,x,\gamma )$ ${\ displaystyle (q, x, \ gamma)}$ $(q, x, \ gamma)$ este acceptare dacă $x=\varepsilon$ ${\ displaystyle x = \ varepsilon}$ $x = \ varepsilon$ Și $q$ ${\ displaystyle q}$ $q$ aparține lui $F.$ ${\ displaystyle F}$ $F.$ . Conform acestei definiții un șir $X$ ${\ displaystyle x}$ $X$ este acceptat de $M.$ ${\ displaystyle M}$ $M.$ dacă și numai dacă la sfârșitul procesării $X$ ${\ displaystyle x}$ $X$ șirul automatului se află într-o stare finală.

În general, cu un automat acționat de baterie $M.$ ${\ displaystyle M}$ $M.$ , limba recunoscută de $M.$ ${\ displaystyle M}$ $M.$ pentru stiva goală este diferită de limba recunoscută de $M.$ ${\ displaystyle M}$ $M.$ pentru starea finală. Cu toate acestea, este important să rețineți că clasa de limbi recunoscute de automatele stivuite nu se schimbă dacă se alege acceptarea pentru stiva goală sau pentru starea finală. Adică, adică $L$ ${\ displaystyle L}$ $L$ este un limbaj acceptat pentru stiva goală de un automat stivuit $M_{1}$ ${\ displaystyle M_ {1}}$ $M_ {1}$ dacă și numai dacă $L$ ${\ displaystyle L}$ $L$ este un limbaj acceptat pentru starea finală de un automat alimentat cu baterie $M_{2}$ ${\ displaystyle M_ {2}}$ $M_ {2}$ . În special, clasa de limbi acceptate de automatele stivei coincide cu cea a limbajelor fără context.

Notă

^ (EN) Dexter C. Kozen, Pushdown Automata , Springer Berlin Heidelberg, 1977, pp. 157–163, DOI : 10.1007 / 978-3-642-85706-5_27 , ISBN 978-3-642-85708-9 . Adus pe 3 noiembrie 2020 .

Alte proiecte

Wikiversitatea conține resurse pentru Automa alimentat de la baterie
Wikimedia Commons conține imagini sau alte fișiere pe Stacked Automa

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] (EN) Dexter C. Kozen, Pushdown Automata , Springer Berlin Heidelberg, 1977, pp. 157–163, DOI : 10.1007 / 978-3-642-85706-5_27 , ISBN 978-3-642-85708-9 . Adus pe 3 noiembrie 2020 .

[1]