Para Σ = {a, b}, consideremos el lenguaje regular
L = {x ∣ x = a2 + 3k or x = b10 + 12k, k ≥ 0}
¿Cuál de los siguientes puede ser una longitud de bombeo (la constante garantizada por el lema de bombeo) para L?
(A) 3
(B) 5
(C) 9
(D) 24
Respuesta: (D)
Explicación: De acuerdo con el Lema de bombeo , debe haber repetición (DFA luego repite algunos estados, y la gramática regular repite su no terminal en la derivación). para todas las picaduras aceptables.
Por lo tanto, la longitud de bombeo mínima debe ser 11 , porque la string con longitud 10 (es decir, w = b 10 ) no repite nada, pero la string con longitud 11 (es decir, w = b 11 ) repetirá estados.
Por lo tanto, la longitud de bombeo para un idioma determinado debe ser superior a 10 , que es 24.
La opción (D) es correcta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA