Considere los siguientes problemas. L(G) denota el lenguaje generado por una gramática G. L(M) denota el lenguaje aceptado por una máquina M.
(I) Para una gramática G no restringida y una string w, si wϵL(G)
(II) Dada una máquina de Turing M, si L(M) es regular
(III) Dadas dos gramáticas G 1 y G 2 , si L(G 1 ) = L(G 2 )
(IV) Dado un NFA N, si existe un PDA determinista tal que N y P acepten el mismo lenguaje
¿Cuál de las siguientes afirmaciones es correcta?
(A) Solo I y II son indecidibles
(B) Solo II es indecidible
(C) Solo II y IV son indecidibles
(D) Solo I, II y III son indecidibles
Respuesta: (D)
Explicación: I, II y III son indecidibles , consulte esto:
Llegando a IV, cada lenguaje regular es Determinista-CFL, que es una propiedad trivial.
La opción (D) es correcta.
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