PUERTA | PUERTA CS 2019 | Pregunta 24

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 ¹⁰ ) no repite nada, pero la string con longitud 11 (es decir, w = b ¹¹ ) 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.

Cuestionario de esta pregunta