Autòmat amb pila

Classes d'autòmates

Un autòmat amb pila és un tipus d'autòmat que utilitza una pila.

Aquests autòmats s'utilitzen en teoria de la computabilitat i són més potents que un autòmat finit però menys capaços que una Màquina de Turing. Si en tot moment només és possible una i només una transició, llavors l'autòmat és un autòmat amb pila determinista. En altre cas, és diu que l'autòmat és un autòmat amb pila general o no determinista.

Els llenguatges que reconeixen els autòmats amb pila pertanyen al grup dels llenguatges lliures del context en la Jerarquia de Chomsky.

Definició formal

Formalment, un autòmat amb pila es pot descriure com una sèptupla $M=(S,\Sigma ,\Gamma ,\delta ,s,Z,F)$ on:

• $S$ és un conjunt finit d'estats.
• $\Sigma$ i $\Gamma$ són alfabets (símbols d'entrada i de la pila respectivament)
• $\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 (q,a,b)=\{(q_{1},\gamma _{1}),(q_{2},\gamma _{2}),\ldots ,(q_{n},\gamma _{n})\}$, amb $q,q_{i}\in S,a\in (\Sigma \cup \{\epsilon \}),b\in \Gamma$, y $\gamma _{i}\in \Gamma ^{*}$ és la següent:

Quan l'estat de l'autòmat és $q$, el símbol que el cap lector està inspeccionant en aquell moment es $a$, i a dalt de la pila trobem el símbol $b$, es fan les següents accions:

• Si $a\in \Sigma$, és a dir, no és la cadena buida, el cap lector avança una posició per inspeccionar el següent símbol
• S'elimina el símbol $b$ de la pila de l'autòmat
• Es seleccionen un parell $(q_{i},\gamma _{i})$ d'entre els existents en la definició de $\delta (q,a,b)$, la funció de transició del autòmat
• S'apila la cadena $\gamma _{i}=c_{1}c_{2}\ldots c_{k}$, amb $c_{i}\in \Gamma$ a la pila del autòmat, quedant el símbol $c_{k}$ a dalt de la pila
• Es canvia el control de l'autòmat a l'estat $q_{i}$