-
Consider the following grammar G :
S → bS|aA|b
A → bA |aB
B → bB|aS| a
Let Na (W) and Nb (W) denote the number of a 's and b 's in a string W respectively.
The language L(G) ⊆ {a, b}+ generated by G is
-
- {W|Na (W) > 3Nb (W)}
- {W|Nb (W) > 3Na (W)}
- {W|Na (W) = 3k, k ∈ {0, 1, 2,...}}
- {W|Nb (W) = 3k, k ∈ {0, 1, 2,...}}
- {W|Na (W) > 3Nb (W)}
Correct Option: C
Here, we have
S → bS
S → baA (S → aA)
S → baaB (A → aB)
S → baaa (B → a)
Therefore, | Na (w) | = 3.
Also, if we use A → bA instead of A → aB,
S → baA
S → babA
To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
S → baA
S → babA
S → babaB
S → babaa
Thus, here also, | Na (w) | = 3. So, C is the correct answer.
