PUERTA | PUERTA-CS-2009 | Pregunta 60 – Part 8

El siguiente DFA acepta el conjunto de todas las strings sobre {0,1} que

(A) comienzan con 0 o 1
(B) terminan con 0
(C) terminan con 00
(D) contienen la substring 00.

Respuesta: (C)
Explicación: si las strings que comienzan con 0 y 1 son 01 y 11 respectivamente, entonces el DFA no los acepta (porque no llega al estado final de terminación/aceptación). Por lo tanto, no la opción A.

Si la string que termina en 0 es 10, entonces DFA tampoco lo acepta. Por lo tanto, no la opción B.

Si la string que contiene la substring 00 es 1001, DFA tampoco la acepta. Por lo tanto, no la opción D.

Ahora, tome cualquier string que termine con 00, como 00, 100, 1100, 10100, 0100, todas son aceptadas por el DFA dado. De ahí la opción C.

Intuitivamente, también podemos observar aquí al observar el DFA que solo hay una ruta directa para alcanzar el estado de terminación final C (digamos que dados 3 estados (círculos) son A, B y C de izquierda a derecha en el diagrama), luego la ruta es A–>B–>C, y esta ruta requiere 00 en la substring actual de la entrada para llegar de A a C.

Ahora, después de llegar a C, la string debe terminar para ser aceptada por el DFA dado, o también puede tener cualquier número de 0 a continuación, para que la string sea aceptada. En cualquiera de los casos, la string terminaría en 00.

Cuestionario de esta pregunta