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 on: és un conjunt finit d'estats. i són alfabets (símbols d'entrada i de la pila respectivament)
é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
Referències
Categoria:Llenguatges formals Categoria:Computabilitat