Lema 2.1
Para cada autómata de pila
existe otro autómata de pila
tal que el lenguaje reconocido por estados finales en el primer autómata es reconocido por pila vacía en el segundo, es decir
Lema 2.2
Para cada autómata de pila
existe otro autómata de pila
tal que el lenguaje reconocido por pila vacía en el primer autómata es reconocido por estados finales en el segundo, es decir