PUERTA | PUERTA-CS-2000 | Pregunta 32

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.

Cuestionario de esta pregunta