Motivación

Ya sabemos $L_{ab}=\{a^nb^n\;\vert\;n\in\bbbn\}$ no es regular (comprobamos con el lema de bombeo o con el teorema de Myhill-Nerode).

Pero $L_{ab}$ es libre de contexto con la siguiente gramática:

$$\begin{eqnarray*} G&=&(\Sigma_N,\Sigma_T,P,\$)\\ &=&(\{\$\},\{a,b\},\{\$\longrightarrow a\$b\vert\epsilon\},\$)\\ \end{eqnarray*}$$

Otro ejemplo parecido es: expresiones matemáticamente correctas de diferentes tipos de paréntesis $\Sigma_T=\{[,],\langle,\rangle,(,)\}$, por ejemplo, $( ( ] ] ) \rangle )$ es incorrecto y $[ ( [ ] ) \langle ( ) \rangle ]$ es correcto.

$$L_{()}=\{w\;\vert\;w\in\Sigma_T^*, w \mbox{ es correcto} \}$$

es libre de contexto, con el sistema de producciones

$$P=\{\$\longrightarrow \$\$\;\vert\;(\$)\;\vert\;[\$]\;\vert\;\langle\$\rangle\;\vert\;\epsilon\}$$

$L_{()}$ no es regular, porque ya $[^n]^n$ no es regular.

¿Podemos construir un tipo de autómata que acepta una palabra de $L_{()}$?

Idea: usamos una pila para memorizar lo que se ha leído:

• Las paréntesis que abren ponemos en la pila.
• Si vemos una parentesis que cierre la cima de la pila tiene que ser su homóloga y la quitamos de la pila.
• Al final, la pila tiene que estar vacía.

Eso era bastante fácil, ampliamos las posibilidades algo más, permitimos

• que el autómata pueda tener varios (número finito) estados (parecido a los AFD, pero veremos que basta con un estado);
• que el autómata sea no-determinista (veremos que habrá una diferencia entre AFPDs y AFPNDs);
• que exista la posibilidad de transiciones $\epsilon$;
• que acepte con pila vacía o con estados finales (veremos que ambas formas son equivalentes);
• que existan más símbolos para la pila;
• que se apile más de un símbolo a la vez;
• que se disponga de un símbolo inicial en la pila.