PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 39

Sea δ la función de transición y α la función de transición extendida del ε-NFA cuya tabla de transición se muestra a continuación:

Entonces, α (q2,aba) es
(A) Ø
(B) {q1, q2, q3}
(C) {q0, q1, q2}
(D) {q0, q2, q3}

Respuesta: (C)
Explicación: La función de transición extendida describe lo que sucede cuando comenzamos en cualquier estado y seguimos cualquier secuencia de entradas.
Dado que este es un NFA épsilon, también debemos considerar los movimientos épsilon y ver qué estados podemos alcanzar después de que finaliza la string de entrada.
El estado inicial es q2, desde q2 la transición con la entrada a está muerta, por lo que debemos buscar la transición épsilon.
Con la transición épsilon llegamos a q0, en q0 tenemos una transición con el símbolo de entrada a, por lo que llegamos al estado q1.
Desde q1 podemos tomar la transición con el símbolo b y llegar al estado q3 pero desde q3 no tenemos más transición con el símbolo a como entrada, por lo que tenemos que tomar otra transición desde el estado q1 que es la transición épsilon que va al estado q2.
Desde q2 llegamos al estado q0 y leemos la entrada b y luego leemos la entrada a y llegamos al estado q1.
Entonces q1 es uno de los estados de la función de transición extendida.
Desde q1 podemos llegar a q2 con epsilon como entrada (mans sin entrada) y desde q2 podemos llegar a q0 con epsilon move, por lo que el estado q2 y q0 también son parte de la función de transición extendida.
Entonces diga q1, q2, q0

Esta solución es aportada por Parul Sharma.

Cuestionario de esta pregunta