Considere los siguientes problemas de decisión:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite
number of stings
¿Cuál de las siguientes afirmaciones es verdadera?
(A) Tanto (P1) como (P2) son decidibles
(B) Ni (P1) ni (P2) son decidibles
(C) Solo (P1) es decidible
(D) Solo (P2) es decidible
Respuesta: (A)
Explicación:
- Una máquina de estados finitos siempre se detiene en el estado final o no final. Por lo tanto, el problema P1 es decidible.
- Verificamos si el lenguaje libre de contexto genera cualquier string de longitud entre n y (2n – 1). Si es así, el lenguaje libre de contexto es infinito, de lo contrario es finito. Por lo tanto, el problema P2 es decidible.
Por lo tanto, la opción (A) es correcta.
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