¿Cuáles de los siguientes son decidibles?
I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free
(A) I y II
(B) I y IV
(C) II y III
(D) II y IV
Respuesta: (B)
Explicación: (A) La intersección de dos lenguajes regulares es regular y verificar si un lenguaje regular es infinito es decidible
(B) Decidir la regularidad de un lenguaje libre de contexto es indecidible.
Comprobamos si L(CFG) contiene alguna string con una longitud entre n y 2n−1, donde n es la constante del lema de bombeo. Si es así, L(CFG) es infinito, de lo contrario es finito.
(C) El problema de igualdad es indecidible para todos los lenguajes excepto en el caso de autómatas finitos, es decir, para lenguajes regulares.
(D) Tenemos que comprobar si la gramática obedece a las reglas de CFG. Si obedece tales reglas, entonces es decidible.
Por lo tanto, la opción (B) es correcta.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
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