Sea L(R) el lenguaje representado por la expresión regular R. Sea L(G) el lenguaje generado por una gramática libre de contexto G. Sea L(M) el lenguaje aceptado por una máquina de Turing M. ¿Cuál de las siguientes decisiones ¿Los problemas son indecidibles?
I. Dada una expresión regular R y una string w, ¿es w∈L(R)?
II. Dada una gramática libre de contexto G, es L(G)=∅
tercero Dada una gramática libre de contexto G, ¿es L(G)=Σ ∗ para algún alfabeto Σ?
IV. Dada una máquina de Turing M y una cuerda w, ¿es w ∈ L(M)?
(A) Solo I y IV
(B) Solo II y III
(C) Solo II, III y IV
(D) Solo III y IV
Respuesta: (D)
Explicación:
- Problema de pertenencia del lenguaje regular -> Decidible
- Vacío de CFL -> Decidible
- L(G)=Σ ∗ problema de CFL -> INdecidible
- Problema de membresía del lenguaje RE -> INdecidible
Por lo tanto, la opción D
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