PUERTA | PUERTA-CS-2004 | Pregunta 88

Considere la siguiente gramática G:

S → bS | aA | b
A → bA | aB
B → bB | aS | a 

Sean Na(w) y Nb(w) el número de a y b en una string w respectivamente. El lenguaje L(G) ⊆ {a, b}+ generado por G es
(A) { w | Na(w) > 3Nb(w)}
(B) { w | Nb(w) > 3Nb(w)}
(C) { w | Na(w) = 3k, k ∈ {0, 1, 2, …}}
(D) { w | Nb(w) = 3k, k ∈ {0, 1, 2, …}}

Respuesta: (C)
Explicación: Aquí tenemos

S → bS
S → baA         (S → aA)
S → baaB     (A → aB)
S → baaa     (B → a)

Por lo tanto, | na (w) | = 3.

Además, si usamos A → bA en lugar de A → aB,

S → baA
S → babA

Para terminar A, tendríamos que usar A → aB ya que solo B termina en a (B → a).

S → baA
S → babA
S → babaB
S → babaa

Así, aquí también, | na (w) | = 3.

 
Entonces, C es la opción correcta.

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

Cuestionario de esta pregunta