1
$\begingroup$

The language of all words over the alphabet {a,b,c} such that

  • the number of as in the word
  • minus the number of cs in the word

is divisible by three.

How is this language regular? Lecturer notes says that it is, and then provides no explanation at all. I tried drawing a DFA for it, but it just seems that the longer the word, the more states there will be and there could be an infinite amount, which is not allowed? Please help, thanks.

$\endgroup$
  • 1
    $\begingroup$ Try this: assume that you've seen as and cs so far s.t. the property holds. Consider what happens if you see one more a. Consider what happens if you see one more c. Do you see why you only need a finite nr. of states? If you don't, consider more possibilities (property holds and then you see 2 more as, etc.). $\endgroup$ – Guildenstern May 26 '14 at 15:02
6
$\begingroup$

All you need to keep track of is the value "number of $a$s seen minus number of $c$s seen", modulo 3 – call that $X$. There are only three different values that $X$ can take. When you see the next character of the input, it's either $a$, $b$ or $c$. Think about how each one affects $X$ and you should be very close to a 3-state automaton that accepts the language you're interested in.

$\endgroup$
  • $\begingroup$ Thank you, you and Guildenstern in the comments helped me work it out. There was a similar example of a DFA in some other notes involving the language of words over the alphabet {0,1}, which when viewed as a binary number, is divisible by 3. Used the same idea with modulus. I've now subsequently drawn a successful DFA for it. Could I be right in assuming that the larger the number n they ask to be divisible by, the more states there are for mod(0) - mod(n-1) in the DFA? $\endgroup$ – howdoyouturnthison May 26 '14 at 15:47
  • $\begingroup$ Yes: a greater modulus means it can take more values so you need more states to remember. $\endgroup$ – David Richerby May 26 '14 at 15:48

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.