Sea L1 un lenguaje regular, L2 un lenguaje determinista libre de contexto y L3 un lenguaje recursivamente enumerable, pero no recursivo. ¿Cuál de las siguientes afirmaciones es falsa?
(A) L1 ∩ L2 es un CFL determinista
(B) L3 ∩ L1 es recursivo
(C) L1 ∪ L2 no tiene contexto
(D) L1 ∩ L2 ∩ L3 es recursivamente enumerable
Respuesta: (B)
Explicación:
(A) Esta afirmación es cierto porque los lenguajes libres de contexto determinista se cierran bajo la intersección con los lenguajes regulares.
(B) Esta afirmación es falsa porque L1 es recursiva y todo lenguaje recursivo es decidible. L3 es recursivamente enumerable pero no recursivo. Entonces, L3 es indecidible. La intersección del lenguaje recursivo y el lenguaje recursivo enumerable es recursivamente enumerable.
(C) Esta afirmación es verdadera porque L1 es regular. Todo lenguaje regular es también un lenguaje libre de contexto. L2 es un lenguaje libre de contexto determinista y cada DCFL también es un lenguaje libre de contexto. Cada lenguaje libre de contexto está cerrado bajo Unión.
(D) Esta declaración es verdadera porque L1 es regular, por lo tanto, también es recursivamente enumerable. L2 es un lenguaje libre de contexto determinista, por lo que también es recursivamente enumerable. Los lenguajes recursivamente enumerables se cierran bajo la intersección.
Por lo tanto, el problema mencionado en la opción (A) es indecidible.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
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