En esta respuesta se menciona
Un lenguaje normal puede ser reconocido por un autómata finito. Un lenguaje sin contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina Turing completa) .
Quería saber sobre la verdad de la parte audaz anterior. ¿De hecho es cierto o no? ¿Cuál es una buena manera de llegar a una respuesta a esto?
Respuestas:
Dos pedazos a esta respuesta;
En primer lugar, la clase de lenguajes reconocidos por Turing Machines no es sensible al contexto , es recursivamente enumerable (sensible al contexto es la clase de lenguajes que obtienes de los autómatas lineales ).
La segunda parte, suponiendo que ajustemos la pregunta, es que sí, un PDA de dos conjuntos es tan poderoso como un TM. Es un poco más simple suponer que estamos usando el modelo de TM que tiene una cinta que es infinita solo en una dirección (aunque ambas direcciones no son mucho más difíciles y equivalentes).
Para ver la equivalencia, piense en la primera pila como el contenido de la cinta a la izquierda de la posición actual, y la segunda como el contenido a la derecha. Empiezas así:
Ahora puede ignorar la entrada y hacer todo sobre el contenido de las pilas (que es simular la cinta). Aparece para leer y presiona para escribir (para que pueda cambiar la "cinta" presionando algo diferente a lo que lee). Luego, podemos simular la TM haciendo estallar desde la pila derecha y empujando hacia la izquierda para mover hacia la derecha, y viceversa para mover hacia la izquierda. Si tocamos la parte inferior de la pila izquierda, nos comportamos en consecuencia (detener y rechazar, o permanecer donde usted, según el modelo), si tocamos la parte inferior de la pila derecha, simplemente empujamos un símbolo en blanco hacia la izquierda.
Para una prueba formal completa, vea la respuesta a otra pregunta .
La relación de la otra manera debería ser aún más obvia, es decir, que podemos simular un PDA de dos pilas con un TM.
fuente