Definición de Autómata de Pila

También son conocidos como autómatas “push-down”. Permiten analizar palabras para reconocer si pertenecen o no a LIC. Tienen la misma estructura que los autómatas finitos (AF), pero se les agrega una pila (memoria auxiliar con método LIFO) para poder guardar información que podrá ser útil en momentos posteriores del análisis.

Son más poderosos que los AF, porque además de reconocer a los lenguajes regulares (LR) tienen la capacidad de reconocer a los lenguajes independientes del contexto (LIC).

Por ejemplo: balanceo de paréntesis (por cada paréntesis de apertura debe existir posteriormente un paréntesis de cierre). Este aspecto es imposible de controlar con un AF.

Los AP, al disponer de memoria auxiliar (pila), pueden introducir en ella un elemento en la pila por cada paréntesis de apertura leído, e ir eliminando de la pila un elemento por cada paréntesis de cierre leído, y, por tanto, llevar el control de sí se han cerrado todos o no.

Definición formal

Formalmente un autómata de pila se define como una 7-upla: M = <Σ, Ґ, Q, q0, p0, F, δ>

  1. Σ: alfabeto (conjunto finito de símbolos) de la cadena de entrada.
  2. Ґ: alfabeto (conjunto finito de símbolos) de pila. Puede tener símbolos en común con Σ. (Algunos autores Σ ∩ Ґ = Ø)
  3. Q: conjunto finito de estados.
  4. q0: estado inicial. q0 ∈ Q.
  5. p0: símbolo inicial de pila, que aparece en el tope de la pila. p0 ∈ Ґ. Ejemplo: $, #, Z0
  6. F: conjunto de estados finales o estados de aceptación. F ⊆ Q.
  7. δ: función de transición entre estados. Se define: δ: Q x Σ U {λ} x Ґ* -> Q x Ґ* (para algunos autores siempre hay que sacar un solo símbolo de la pila) Básicamente leo, saco y pongo en la pila

Por cada estado, símbolo de entrada o palabra vacía (λ), y símbolo en el tope de la pila, determina la transición a otro estado y decide que se debe escribir en la pila.

La pila puede encontrarse o no inicializada con el símbolo inicial de pila (también llamado distinguido), es decir, cuando la pila está vacía se puede leer en su tope el valor de p0.

Ejemplo de transición: primero aparece lo que leo, después lo que saco y por último lo que pongo en la pila

Untitled