PUERTA | Puerta TI 2005 | Pregunta 37

Considere el autómata finito no determinista (NFA) que se muestra en la figura.

El estado X es el estado inicial del autómata. Deje que el idioma aceptado por la NFA con Y como el único estado de aceptación sea L1. De manera similar, deje que el idioma aceptado por la NFA con Z como el único estado de aceptación sea L2. ¿Cuál de las siguientes afirmaciones sobre L1 y L2 es VERDADERA?

Corrección en cuestión:
hay un borde de Z->Y etiquetado como 0 y otro borde de Y->Z etiquetado como 1, en lugar de los bordes con doble flecha y sin flecha.

(A) L1 = L2
(B) L1 ⊂ L2
(C) L2 ⊂ L1
(D) Ninguna de las anteriores

Respuesta: (A)
Explicación: Según el teorema de Arden ,

Para y como estado final:

Y = X0 + Y0 + Z1 

Para z como estado final:

Z = X0 + Y0 + Z1 

Por eso,

L(Y) = L(Z) 

Entonces, la opción (A) es correcta.

Cuestionario de esta pregunta