1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – James Pekon Feb 14 at 1:33
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Feb 14 at 9:45

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.