# Autòmat amb pila

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}$

## Referències

* ↑ Hopcroft, J.E.; Ullman, J.D. «Nonerasing stack automata». Journal of Computer and System Sciences, 1, 2, pàg. 166–186. DOI: 10.1016/s0022-0000(67)80013-8.
* ↑ 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :