AP = (Σ, Γ, Q, A0, q0, f, F) donde:
Σ es el alfabeto de símbolos de entrada
Γ es el alfabeto de símbolos de pila
Q es un conjunto finito de estados
A0 ∈ Γ es el símbolo inicial de la pila (un único símbolo)
q0 ∈ Q es el estado inicial del autómata
F es el conjunto de estados de aceptación o estados finales
f es la función de transición de ternas (estado, símbolo de entrada o λ, símbolo de pila) en el conjunto de las partes Q × Γ*
Caracteristicas:
- Ayudan a representar lenguajes que son difíciles o imposibles de representar con Autómatas Determinísticos.
- Los autómatas de pila son capaces de representar cualquier lenguaje independiente de contexto.
- Al cambiar de estado también cambia la cima de la pila.
- Alcance de los lenguajes libres de contexto
Lema de bombeo- muestra como en algunos lenguajes independientes del contexto pueden producirse cadenas “bombeando” porciones de otras cadenas. - Si L es un lenguaje independiente de contexto que contiene un número infinito de cadenas, entonces debe existir en L una cadena que tenga la forma svuwt, donde s, v, u, w y t son subcadenas, por lo menos una de v y w es no vacía, y svnuwnt está en L para cada
Representación de {a^n b^n }
M:(
Σ={a,b},
Γ={A,B},
Q= {q0, q1},
A0=Z,
q0=q0,
F=q3,
f(q0, a, λ)={[q0,A]},
f(q0, b, A)={[q1, λ]},
f(q1, b, A)={[q1, λ]})