¿Cuál de las siguientes es FALSA?
(A) Existe un DFA mínimo único para cada idioma regular
(B) Cada NFA se puede convertir en un PDA equivalente.
(C) El complemento de todo lenguaje libre de contexto es recursivo.
(D) Todo PDA no determinista se puede convertir en un PDA determinista equivalente.
Respuesta: (D)
Explicación: El poder del PDA determinista no es lo mismo que el poder del PDA no determinista. El PDA determinista no puede manejar lenguajes o gramáticas con ambigüedad, pero NDPDA puede manejar lenguajes con ambigüedad y cualquier gramática libre de contexto. Por lo tanto, cada PDA no determinista no se puede convertir en un PDA determinista equivalente.
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