The grammar with production rules S → aSb | SS | λ generates language L given…
2013
The grammar with production rules S → aSb | SS | λ generates language L given by:
- A.
L = { w ∈ {a, b}* | nₐ(w) = n_b(w) and nₐ(v) ≥ n_b(v) where v is any prefix of w }
- B.
L = { w ∈ {a, b}* | nₐ(w) = n_b(w) and nₐ(v) ≤ n_b(v) where v is any prefix of w }
- C.
L = { w ∈ {a, b}* | nₐ(w) ≠ n_b(w) and nₐ(v) ≥ n_b(v) where v is any prefix of w }
- D.
L = { w ∈ {a, b}* | nₐ(w) ≠ n_b(w) and nₐ(v) ≤ n_b(v) where v is any prefix of w }
Attempted by 21 students.
Show answer & explanation
Correct answer: A
The grammar S → aSb | SS | λ generates balanced strings where every 'a' is matched by a subsequent 'b'. This requires total counts nₐ(w) = n_b(w).
For prefixes, the rule ensures 'a's precede matching 'b's, so nₐ(v) ≥ n_b(v). Option A correctly captures this condition.
A video solution is available for this question — log in and enroll to watch it.