CGU-NET | UGC NET CS 2017 Ene – III | Pregunta 62

¿Cuáles de los siguientes pares tienen diferente poder expresivo?
(A) Máquina de turing de una sola cinta y máquina de turing multidimensional.
(B) Máquina de turing multicinta y máquina de turing multidimensional.
(C) Autómatas pushdown deterministas y autómatas pushdown no deterministas.
(D) Autómatas finitos deterministas y autómatas finitos no deterministas

Respuesta: (C)
Explicación:

1. La máquina de turing de una sola cinta y la máquina de turing multidimensional tienen el mismo poder expresivo.
2. La máquina de turing multicinta y la máquina de turing multidimensional tienen el mismo poder expresivo.
3. Los autómatas de empuje hacia abajo deterministas y los autómatas de empuje hacia abajo no deterministas tienen un poder expresivo diferente (n-pda es más expresivo)
4. Los autómatas finitos deterministas y los autómatas finitos no deterministas tienen el mismo poder expresivo.

Entonces, la opción (C) es correcta.

Cuestionario de esta pregunta