PUERTA | Puerta TI 2005 | Pregunta 39

Considere la gramática regular:

S → Xa | Ya
X → Za
Z → Sa | ϵ
Y → Wa
W → Sa

donde S es el símbolo inicial, el conjunto de terminales es {a} y el conjunto de no terminales es {S, W, X, Y, Z}.
Deseamos construir un autómata finito determinista (DFA) para reconocer el mismo lenguaje. ¿Cuál es el número mínimo de estados requeridos para el DFA?
(A) 2
(B) 3
(C) 4
(D) 5

Respuesta: (B)
Explicación:
El lenguaje producido por la gramática dada es:
L = { aa, aaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaaa ……}

Será no producir strings de longitud 1, 4, 8….

Por lo tanto, la string mínima es ‘aa’.
Entonces, los estados mínimos requeridos para construir autómatas para este lenguaje son 3.

 
Por lo tanto, la opción (B) es correcta.

 
Comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta