Usuari:Mcapdevila/Autòmat amb pila

Un autòmat amb pila , autòmat a pila o autòmat de pila és un model matemàtic d'un sistema que rep una cadena constituïda per símbols d'un alfabet i determina si aquesta cadena pertany al llenguatge que el autòmat reconeix. El llenguatge que reconeix un autòmat amb pila pertany al grup dels llenguatges lliures de context en la classificació de la Jerarquia de Chomsky.

Definició formal

Formalment, un autòmat amb pila pot ser descrit com una septuplica $M=(S,\Sigma ,\Gamma ,\delta ,s,Z,F)$ on:

• Σ i $\Gamma$ són alfabets d'entrada, de la cadena i de la pila respectivament;
• S un conjunt de estats;
• $\Delta :S\times (\Sigma \cup \{\epsilon \})\times \Gamma \rightarrow {\mathcal {P}}(S\times \Gamma ^{*})$
• $S\in S$ és l'estat inicial;
• $Z\ \in \Gamma$ és el símbol inicial de la pila;
• $F\subseteq S$ és un conjunt d'estats d'acceptació o finals.

La interpretació de $\delta (s,a,Z)=\{(s_{1},\gamma _{1}),(s_{2},\gamma _{2}),\ldots ,(s_{n},\gamma _{n})\},$ amb $s,p_{i}\in Q,a\in (\Sigma \cup \{\epsilon \}),\gamma _{i}\in \Gamma$ és la següent:

Quan l'estat de l'autòmat és $s$, el símbol que el cap lector està inspeccionant en aquest moment és $a$, i al cim de la pila ens trobem el símbol $Z$, es realitzen les següents accions:

• Si $a\in \Sigma$, és a dir no és la paraula buida, s'avança una posició el cap lector per inspeccionar el següent símbol.
• S'elimina el símbol Z de la pila de l'autòmat.
• Se selecciona un parell $(p_{i},\gamma _{i})$ d'entre els existents en la definició de $\delta (s,A,Z)$, la funció de transició de l'autòmat.
• Es apila la cadena $\gamma _{i}=A_{1}A_{2}\ldots a_{k}$ a la pila de l'autòmat, quedant el símbol $A_{1}$ al cim de la pila.
• Es canvia el control de l'autòmat a l'estat $p_{i}$.

Funcionament

Els autòmats de pila, en forma similar a com s'usen els autòmats finits, també es poden utilitzar per acceptar cadenes d'un llenguatge definit sobre un alfabet A. Els autòmats de pila poden acceptar llenguatges que no poden acceptar els autòmats finits. Un autòmat de pila té una cinta d'entrada i un mecanisme de control que pot trobar-se en un d'entre un nombre finit d'estats. Un d'aquests estats es designa com estat inicial, ia més alguns estats es diuen d'acceptació o finals. A diferència dels Autòmats finits, els autòmats de pila compten amb una memòria auxiliar anomenada pila. Els símbols (anomenats símbols de pila) poden ser inserits o extrets de la pila, d'acord amb el maneig last-in-first-out (LIFO). Les transicions entre els estats que executen els autòmats de pila depenen dels símbols de entrada i dels símbols de la pila. L'autòmat accepta una cadena x si la seqüència de transicions, començant en estat inicial i amb pila buida, condueix a un estat final, després de llegir tota la cadena x.

Representació

Una màquina d'aquest tipus es representa de la següent forma

Igual que un autòmat finit un autòmat de pila té un flux d'entrada i un flux de control que pot trobar-se en un d'entre un nombre finit d'estats. Un d'aquests estats es designa com l'inicial i almenys un estat és d'acceptació.

La principal diferència és que els autòmats de pila compten amb una pila on poden emmagatzemar informació per recuperar-la més tard.

Els símbols que poden emmagatzemar-se en aquesta pila es coneixen com a símbols de pila de la màquina, constitueixen un conjunt finit que pot incloure alguns símbols definint l'alfabet de la màquina i potser alguns símbols addicionals que s'utilitzen com a marques internes. Si una màquina s'insereix un símbol especial a la pila abans d'efectuar algun altre càlcul, llavors aquest símbol al cim de la pila pot usar-se com a indicador de pila buida per a càlculs posteriors, aquest símbol és #.

Exemple

Sigui el següent LLC $L=\{a^{k}b^{k}|k\geq 0\}$, format per les cadenes $L=\{\epsilon ,ab,aabb,aaabbb,aaaabbbb,\ldots \}$

Aquest llenguatge pot ser reconegut pel següent autòmat amb pila:

$M=(\{q_{0},q_{1},q_{2},q_{3}\},\{a,b\},\{A,{\underline {A}}\},\delta ,q_{0},\{q_{0},q_{3}\}),$

on les transicions són:

$\delta (q_{0},a,\epsilon )=\{(q_{1},{\underline {A}})\}$

$\delta (q_{1},a,\epsilon )=\{(q_{1},{\underline {A}})\}$

$\delta (q_{1},b,{\underline {A}})=\{(q_{2},\epsilon )\}$

$\delta (q_{1},b,{\underline {A}})=\{(q_{3},\epsilon )\}$

$\delta (q_{2},b,{\underline {A}})=\{(q_{2},\epsilon )\}$

$\delta (q_{2},b,{\underline {A}})=\{(q_{3},\epsilon )\}$

$\delta (q,\theta ,\rho )=\emptyset$ per a qualsevol $(q,\theta ,\rho )$

El significat de les transicions pot ser explicat analitzant la primera transició:

$\delta (q_{0},a,\epsilon )=\{(q_{1},{\underline {A}})\}$

on $q_{0}$ és l'estat actual, $a$ és el símbol a l'entrada i $\epsilon$ s'extreu del cim de la pila. Llavors, l'estat de l'automat canvia a $q_{1}$ i el símbol ${\underline {A}}$ es posa al cim de la pila.

La idea del funcionament de l'autòmat és que en anar llegint els diferents símbols a, aquests passen a la pila en forma de símbols A. En aparèixer el primer símbol b a l'entrada, es comença el procés de desapilat, de manera que coincideixi el nombre de símbols b llegits amb el nombre de símbols A que apareixen a la pila.

Autòmat amb pila determinista

Noteu que, a diferència d'un autòmat finit o una màquina de Turing, la definició bàsica d'un autòmat amb pila és de naturalesa no determinista, doncs la classe dels autòmats amb pila deterministes, a diferència del que passava amb aquells models, té una potència descriptiva estrictament menor. Per qualificar un autòmat amb pila com determinista s'han de donar dues circumstàncies: en primer lloc, per descomptat, que en la definició de cada component de la funció de transició existeixin un únic element el que dóna la naturalesa determinista. Però això no és suficient, ja que a més pot donar-se la circumstància que l'autòmat estigui en l'estat $s$ i en la pila aparegui el símbol $SZ$, llavors, si hi ha una definició de transició possible per a algun símbol qualsevol $a$ de l'alfabet d'entrada, però, a més hi ha una altra alternativa per a la paraula buida $\epsilon$, també això és una forma de no determinisme, doncs podem optar entre llegir un símbol o no fer-ho. Per això, en autòmat determinista no ha d'existir transició possible amb lectura de símbol si pot fer-se sense ella, ni al contrari.

Per a cada $q\in Q,Z\in \Gamma$, es doni que: $\mid \delta (q,\epsilon ,Z)\mid +\mid \delta (q,a,Z)\mid \leq 1$, per a cada $a\in \Sigma$

Definició

Un autòmat amb pila determinista (AFPD) és una 7-UPLA,

P = (Q, Σ, Г, Δ, q0, T, Z) on:

• Q és un conjunt finit d'estats.
• Σ és l'alfabet d'entrada.
• Г és l'alfabet de la pila.
• Q0 є Q és l'estat inicial.
• Z є Г símbol inicial de la pila.
• T és subconjunt de Q (conjunt d'estats finals).
• Δ és la funció de transició tal que:

Δ: Q × (Σ U{ε}) × Г → (Q × Г *)

Observació

En un moment, la unitat de control de l'autòmat escaneja un símbol 'a' sobre la cinta d'entrada i el símbol 's'al límit de la pila.

Aquest pas computacional representa: La unitat de control passa a 'q0' i es mou a la dreta a la cinta d'entrada, esborra el símbol 's'del límit, escriu a la cadena i passa a escanejar el nou límit.

Autòmat amb pila no determinista

Un autòmat finit amb pila no determinista (AFPN) consta dels mateixos paràmetres d'un AFPD.

P = (Q, Σ, Г, Δ, q0, T, Z):

On la funció de transició Δ és de la forma:

Δ: Q × (Σ U{ε}) × Г → Pf (Q × Г *)

On Pf (Q × Г *) és un conjunt de subconjunts finits de Q × Г *

Per q є Q, a є Σ U{ε}i es є Г

Δ (q, a, s) ={(q1, γ1), (q2, γ 2),. . . , (Qn, γ n)}

On γi є Г *

Exemple

Dissenyar un AFPN que accepti el llenguatge $\{a^{i}b^{i}:i\geq 0\}$ <ref> Universitat del Valle, Exemples

Sobre:

Σ ={a, b}

• Δ (q0, a, Z) = (q0, AZ)
• Δ (q0, ε, Z) = (q2, Z) (accepta ε)
• Δ (q0, a, A) = (q0, AA)
• Δ (q0, b, A) = (q1, ε)
• Δ (q1, b, A) = (q1, ε)
• Δ (q1, ε, Z) = (q2, Z)

El no determinisme es dóna per la presència simultània de:

Δ (q0, a, Z) i Δ (q0, ε, Z)

Referències

Bibliogràfica

• Teoria d'autòmats i llenguatges formals.

Autòmats i complexitat. Kelly Dean Editorial Prentice Hall

• Introducció a la teoria d'autòmats, llenguatges i computació

John I. Hopcroft; Jeffrey D. Ullman Editorial Cecs

• Teoria de la computació

J. Gleuu Brokshear Editorial Addison Wesley Iberoamericana

Enllaços externs

• Ciències de la Computació I