# Does there exist a finite automaton for the given language?

The question is simple and given as, alphabet $$A$$ is $$\{a, b\}$$, and language $$L$$ over $$A$$:

$$L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$$. Here $$n(a)$$ = number of $$a$$ and $$n(b)$$ is number of $$b$$.

My answer is that it's not a regular language because the modular expression can be simplified as. $$n(a) =n(b) +3k+1$$ and hence there is a comparison in between the two alphabets. Further comparison are infinite but a finite automaton has only finite memory which are associated with states.

So we can say the above language is not regular hence no finite automaton for it. But there is a problem, I have read a book by Linz in which the above question was given stating that find the regular expression for it. I am a bit confused so any help will be appreciated. I would also be interested in a general approach to answer this type of question.

• "because the modular expression can be simplified as [something] and hence there is a comparison in between the two alphabets" -- that sentence doesn't make any sense to me. Which to alphabets? What kind of "comparison"? – Raphael Sep 28 '18 at 9:22
• @Raphael "alphabet" should be "symbol" and I think it's trying to convey the intuition that the language can't be regular for basically the same reason that $\{a^nb^n\mid n\geq 0\}$ isn't: you have to remember how many $a$s and $b$s you've seen and you'd need infinitely many different states to cover the infinite number of possibilities. (In this case, the intuition is incorrect, but I that's what it's getting at.) – David Richerby Sep 28 '18 at 11:34
• @DavidRicherby Ah, gotcha. The "because" threw me since there is no kind of reasonable reasoning (be-dum-dum-tss) here. – Raphael Sep 28 '18 at 11:36
• Very similar: cs.stackexchange.com/questions/74741/… (since $a+2b$ and $a-b$ are identical mod 3) – rici Sep 28 '18 at 17:40

## 2 Answers

Your reasoning about comparisons would be correct, if there were infinitely many numbers. But there's only three of them modulo $$3$$.

The automaton can be constructed directly. You need three states, one for each of the residues: $$0$$, $$1$$ and $$2$$. Then every $$a$$-transition should correspond to an increment and $$b$$-transition to a decrement.

• i have tried that way but i was unable to form dfa since in last state(remainder =2 ) where addition of a leads to first state of remainder 0 and b leads to one decreament. but what about addition of b at state having remainder 0 and if we do so then the equation is unstatisfied – Noob Sep 28 '18 at 8:16
• @low_burning $2$ and $-1$ are the same modulo $3$. – Dmitri Urbanowicz Sep 28 '18 at 8:41
• thanks and i really appreciate its been a while since i get rid of this stuff , thanks – Noob Sep 28 '18 at 8:56

As Dimitri has already said, the number of comparisons will only be 3. Consider the three states: q0 - where the n(a) - n(b) mod 3 = 0

q1 - where n(a) - n(b) mod 3 = 1

q2 - where n(a) -n(b) mode 3 = 2

Out of these q1 will be final state.

The DFA will be:

Note: If we get n(b) more than n(a). say n(a) is 0 and n(b) is 2, the automaton still works as -2 mod 3 is 1.