# Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}

I am doing a problem where I need to prove that no 2-state DFA decides the language A = {x ∈ {0, 1}*| bnum(x) is divisible by 3}.

It's seems pretty obvious at first, because aren't there only 4 DFA's with two states that define it? Also, since x is divisible by 3, the DFA would need to have 3 states to define the remainder values.

So I feel like I have a good understanding of the problem, but how do I more formally prove the statement? Any help is appreciated.

## 1 Answer

Remainder values is indeed the clue! Obviously the strings $$1$$ and $$10$$ cannot end in a final state as they represent number 1 and 2 respectively. But can they end in the same state?

• Arent 1 and 10 both remained of 1, so they both go in the R1 state. and 2, 11 would be in the R2 state. Right? – James Pekon Feb 14 '19 at 1:33
• Are you reading the bits in binary numbers in the same direction as I do? I was assuming 1, 10, 11, 100, 101, 110, etc. – Hendrik Jan Feb 14 '19 at 9:45