¿Cuáles de los siguientes pares tienen DIFERENTE poder expresivo?
(A) Autómatas finitos deterministas (DFA) y Autómatas finitos no deterministas (NFA)
(B) Autómatas de empuje hacia abajo deterministas (DPDA) y Autómatas de empuje hacia abajo no deterministas (NPDA)
(C) Máquina de Turing de cinta única determinista y Autómatas no deterministas Máquina de Turing determinista de una sola cinta
(D) Máquina de Turing de una sola cinta y máquina de Turing de varias cintas
Respuesta: (B)
Explicación:
NDPDA puede manejar lenguajes o gramáticas con ambigüedad, pero DPDA no puede manejar lenguajes con ambigüedad y cualquier gramática libre de contexto.
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