Finding context-free grammar

Question

I've had quite a problem with this task:

L = {w element of {a,b}* | 
       the number of a's plus 2 times the number of b's modulo 5 in w is 0}

I thought about:

S -> ε

S -> abbS

S -> babS

S -> bbaS

S -> aaaaaS

S -> aaabS

etc...

But that can't be the optimal solution since you'd also have to shift the positions of the S and it would generate way too many cases. Also it would just be an enumeration of the cases rather then a "general solution" which is clearly not the goal.

Answer 1

I'd suggest introducing auxiliary non-terminal symbols:

• M5 = the number of a's plus 2 times the number of b's modulo 5 in w is 0
• M4 = the number of a's plus 2 times the number of b's modulo 4 in w is 0
• M3 = the number of a's plus 2 times the number of b's modulo 3 in w is 0
• M2 = the number of a's plus 2 times the number of b's modulo 2 in w is 0

Then the grammar can be expressed as follows:

S -> ε
S -> M5 S

M5 -> a M4
M5 -> M4 a
M5 -> b M3
M5 -> M3 b

M4 -> a M3
M4 -> M3 a
M4 -> b M2
M4 -> M2 b

M3 -> a M2
M3 -> M2 a
M3 -> b a
M3 -> a b

M2 -> a a
M2 -> b