Consider the following grammar G: S → bS | aA | b A → bA | aB B → bB | aS | a…
2004
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
- 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, ...}}
Attempted by 79 students.
Show answer & explanation
Correct answer: C
Key insight: every time the grammar returns to S via the a-productions it produces exactly three a's.
Follow the a-production path: S → aA → aB → aS. These three productions contribute one a each, so that path yields exactly three a's and returns to S.
If instead of B → aS we take B → a, the same three a's are produced and the derivation terminates. There are no other productions that introduce a's, so every derivation adds a's in blocks of three.
Each nonterminal also allows insertion of any number of b's (S → bS or S → b, A → bA, B → bB), so b's can appear arbitrarily between or around the a's without affecting the count of a's.
A string with no a's is possible (for example repeated S → bS followed by S → b), so Na(w) = 0 is allowed.
Conclusion: the language consists exactly of nonempty strings over {a,b} whose number of a's is a multiple of 3.
Formally: L(G) = { w ∈ {a,b}+ | Na(w) = 3k for some integer k ≥ 0 }.
A video solution is available for this question — log in and enroll to watch it.