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.^[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]

Definició formal

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

• ${\displaystyle S}$ és un conjunt finit d'estats.
• ${\displaystyle \Sigma }$ i ${\displaystyle \Gamma }$ 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 ^{*})}$
• ${\displaystyle s\in S}$ és l'estat inicial
• ${\displaystyle Z\ \in \Gamma }$ és el símbol inicial de la pila
• ${\displaystyle F\subseteq S}$ és un conjunt d'estats d'acceptació o finals

La interpretació de ${\displaystyle \delta (q,a,b)=\{(q_{1},\gamma _{1}),(q_{2},\gamma _{2}),\ldots ,(q_{n},\gamma _{n})\}}$, amb ${\displaystyle q,q_{i}\in S,a\in (\Sigma \cup \{\epsilon \}),b\in \Gamma }$, y ${\displaystyle \gamma _{i}\in \Gamma ^{*}}$ és la següent:

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

• Si ${\displaystyle 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 ${\displaystyle b}$ de la pila de l'autòmat
• Es seleccionen un parell ${\displaystyle (q_{i},\gamma _{i})}$ d'entre els existents en la definició de ${\displaystyle \delta (q,a,b)}$, la funció de transició del autòmat
• S'apila la cadena ${\displaystyle \gamma _{i}=c_{1}c_{2}\ldots c_{k}}$, amb ${\displaystyle c_{i}\in \Gamma }$ a la pila del autòmat, quedant el símbol ${\displaystyle c_{k}}$ a dalt de la pila
• Es canvia el control de l'autòmat a l'estat ${\displaystyle q_{i}}$

Referències