Con respecto al poder de reconocimiento de idiomas, ¿cuál de las siguientes afirmaciones es falsa?
(A) Los autómatas de estado finito no deterministas son equivalentes a los autómatas de estado finito deterministas.
(B) Los autómatas pushdown no deterministas son equivalentes a los autómatas pushdown deterministas.
(C) Las máquinas de Turing no deterministas son equivalentes a las máquinas de Turing deterministas.
(D) Las máquinas de Turing de varias cintas son equivalentes a las máquinas de Turing de una sola cinta.
Respuesta: (B)
Explicación: Los autómatas pushdown no deterministas NO son equivalentes a los autómatas pushdown deterministas.
La opción (B) es falsa.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA