Problem Detail: 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.
Asked By : howdoyouturnthison
Answered By : David Richerby
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/26115 Ask a Question Download Related Notes/Documents
