A regular grammar for the language L = { aⁿ bᵐ | n is even and m is even } is…
2013
A regular grammar for the language
L = { aⁿ bᵐ | n is even and m is even } is given by
- A.
S → aSb | S₁
S₁ → bS₁a | λ - B.
S → aaS | S₁
S₁ → bSb | λ - C.
S → aSb | S₁
S₁ → S₁ab | λ - D.
S → aaS | S₁
S₁ → bbS₁ | λ
Attempted by 22 students.
Show answer & explanation
Correct answer: D
The language L requires strings with an even number of 'a's followed by an even number of 'b's.
To enforce even 'a's, the start symbol S can use the rule S → aaS | A.
To enforce even 'b's, the non-terminal A can use the rule A → bbA | ε.
This sequential generation ensures the final string matches the pattern a^2n b^2m exactly.
A video solution is available for this question — log in and enroll to watch it.