1
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

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).

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Victor Brunell Feb 6 '15 at 1:51
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 6 '15 at 1:54
  • $\begingroup$ Ah, got it! I thought -1mod3=1, but it's -2mod3=1. That threw my DFA construction off. Thank you for the help! $\endgroup$ – Victor Brunell Feb 6 '15 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.