¿Cuál de las siguientes afirmaciones es/son VERDADERAS?
(A)
Todo subconjunto de un lenguaje recursivamente enumerable es recursivo.
(B)
Si un lenguaje L y su complemento L son recursivamente enumerables, entonces L debe ser recursivo.
(C)
El complemento de un lenguaje libre de contexto debe ser recursivo
(D)
Si L1 y L2 son regulares, entonces L1∩ L2 debe ser determinista sin contexto
Respuesta: (B) (C) (D)
Explicación:
Opción A: No se cierra ningún idioma en la operación de subconjunto. Entonces, un subconjunto en un idioma RE puede o no ser REC. Por lo tanto, la opción A es falsa.
Opción B: Si L y \bar Lare ambos RE ⇒ L es REC es un teorema y es verdadero. (LFC) C = (CSL) C = CSL
Opción C: cada CSL es recursivo. Entonces, el complemento de CFL es recursivo y es cierto.
Opción D: L 1 \to regular, L 2 \to regular
L 1 ∩L 2 = Regular ∩ Regular = Regular
Ahora cada lenguaje regular es un DCFL. Entonces, la opción D también es cierta.
Cuestionario de esta pregunta
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