# Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is:

Find a regular grammar that generates each of the following languages: $$L = \{ w \in {a,b}^* \mid \text{na}(w) – \text{nb}(w) = 1 \mod 3 \} ,$$

where $\text{na}(w)$ is the number of $a$s and $\text{nb}(w)$ the number of $b$'s occurring in $w$, respectively.

It seems as though a DFA can't accept this language since any difference of $a$'s and $b$'s resulting in 1 will be in the language, but that gives an infinite number of possibilities.

Any help pointing me in the right direction for this problem would be much appreciated.

Hint: How many states do you need to keep track of $n_a(w)-n_b(w) \pmod{3}$, where $w$ is any prefix of the input? Consider how many possibilities this quantity has, and whether knowing the value for a word $w$ helps you calculate the value for the word $w\alpha$ ($\alpha$ being a single symbol).

• I'm thinking I need 3 states for mod3 since I can only have remainders 0,1,2. From there, I don't quite follow. Sorry, I'm new to this subject. Feb 6 '15 at 1:51
• Right, you only need 3 states. You'll have to make the rest of the effort yourself. I won't answer any more questions. You're getting pretty close, and I'm sure you can finish solving the exercise on your own. Feb 6 '15 at 1:54
• Ah, got it! I thought -1mod3=1, but it's -2mod3=1. That threw my DFA construction off. Thank you for the help! Feb 6 '15 at 3:55