Lema 2.1
Para cada autómata de pila
![$\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$](img1728.gif)
existe otro autómata de pila
![$\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$](img1743.gif)
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
![$\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$](img1728.gif)
existe otro autómata de pila
![$\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$](img1743.gif)
tal que el lenguaje reconocido por pila vacía en el primer autómata es reconocido por estados finales en el segundo, es decir