The regular grammar for the language \(L = \{a^{n}b^{m} | \ n + m \ \ is \…
2016
The regular grammar for the language \(L = \{a^{n}b^{m} | \ n + m \ \ is \ even \}\) is given by
- A.
S → S1 | S2
S1 → a S1 | A1
A1 → b A1 | λ
S2 → aaS2 | A2
A2 → b A2 | λ
- B.
S → S1 | S2
S1 → a S1 | a A1
S2 → aa S2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
- C.
S → S1 | S2
S1 → aaa S1 | aA1
S2 → aaS2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
- D.
S → S1 | S2
S1 → aa S1 | A1
S2 → aaS2 | aA2
A1 → bbA1 | λ
A2 → bbA2 | b
Attempted by 28 students.
Show answer & explanation
Correct answer: D
Correct grammar (one valid regular grammar):
S → S1 | S2
S1 → aa S1 | A1
S2 → aa S2 | a A2
A1 → bb A1 | λ
A2 → bb A2 | b
Why this works:
S1 branch: produces an even number of a's (pairs of aa) followed by an even number of b's (pairs of bb), with the b-block allowed to be empty via A1 → λ. Hence n and m are both even, so n+m is even.
S2 branch: produces an odd number of a's (one initial a plus any number of aa pairs) and an odd number of b's (one final b plus any number of bb pairs). Hence n and m are both odd, so n+m is even.
Both branches produce strings of the form a^n b^m (only a's then b's), and every a^n b^m with n+m even falls into exactly one of the two branches. Therefore the grammar generates exactly the target language.
Example derivations:
For a^2 b^2 (aabb): S → S1 → aa S1 → A1 → bb A1 → λ, yielding aabb.
For a^3 b^1 (aaab): S → S2 → aa S2 → a A2 → b, yielding aaab.
A video solution is available for this question — log in and enroll to watch it.