Un autòmat amb pila és un tipus d'autòmat que utilitza una pila.
Classes d'autòmates
(En fer clic a cada capa, apareix un article sobre aquest tema)
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.[1] 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.[2]
Formalment, un autòmat amb pila es pot descriure com una sèptupla
on:
és un conjunt finit d'estats.
i
són alfabets (símbols d'entrada i de la pila respectivament)
![{\displaystyle \delta :S\times (\Sigma \cup \{\epsilon \})\times \Gamma \rightarrow {\mathcal {P}}(S\times \Gamma ^{*})}](//wikimedia.org/api/rest_v1/media/math/render/svg/c4c40260aeb5387fc8e04b909862fac2b70f6e53)
és l'estat inicial
és el símbol inicial de la pila
és un conjunt d'estats d'acceptació o finals
La interpretació de
, amb
, y
és la següent:
Quan l'estat de l'autòmat és
, el símbol que el cap lector està inspeccionant en aquell moment es
, i a dalt de la pila trobem el símbol
, es fan les següents accions:
- Si
, é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
de la pila de l'autòmat
- Es seleccionen un parell
d'entre els existents en la definició de
, la funció de transició del autòmat
- S'apila la cadena
, amb
a la pila del autòmat, quedant el símbol
a dalt de la pila
- Es canvia el control de l'autòmat a l'estat
![{\displaystyle q_{i}}](//wikimedia.org/api/rest_v1/media/math/render/svg/2752dcbff884354069fe332b8e51eb0a70a531b6)