He aquí por qué:
* Definición formal: Un PDA es un dispositivo informático teórico que utiliza una pila para almacenar y recuperar información, además de tener un control de estado finito y una cinta de entrada. Esta capacidad corresponde directamente a la potencia expresiva necesaria para reconocer CFL.
* equivalencia a gramáticas sin contexto: Los PDA son equivalentes en poder a las gramáticas sin contexto. Esto significa que:
* Para cualquier CFL, puede diseñar un PDA que lo acepte.
* Para cualquier PDA, puede construir una gramática sin contexto que genera el lenguaje que acepta.
* Limitaciones: Los PDA no pueden reconocer todos los idiomas. * No pueden * reconocer los idiomas que requieren una memoria más compleja o capacidades computacionales más allá de la pila, como los idiomas sensibles al contexto (que requerirían algo más poderoso como una máquina de turbios).