¿Y si sustituyo una pila por una cola?

Question

Supongamos que tengo una PDA $P$ . ¿Y si sustituyo su pila de Primero en entrar, último en salir por una cola de Primero en entrar, primero en salir?

¿Es esta nueva máquina con cola tan potente como una PDA? ¿Puede representar los mismos idiomas? Creo que sí, porque podemos seguir contando entradas con ella. ¿Tiene sentido?

Answer 1

Sí. No. Con un FIFO se consigue incluso una máquina mucho más potente, equivalente a una máquina de Turing. Intuitivamente, puedes utilizar el FIFO para "girar" la información que contiene, de modo que puedas llegar a todas las posiciones. Eso significa que tienes de hecho una cinta de Turing.