# Finite Automata Question

• Apr 25th 2008, 01:46 AM
farakhkhan@yahoo.com
Finite Automata Question
How can I draw FA over {0, 1} which represent binaries of Integers only divisible by 3 and all leading 0’s are permissible?

• Apr 25th 2008, 08:03 AM
Alvyda
What is FA?
• Apr 25th 2008, 09:52 AM
Isomorphism
Quote:

Originally Posted by farakhkhan@yahoo.com
How can I draw FA over {0, 1} which represent binaries of Integers only divisible by 3 and all leading 0’s are permissible?

Hint:Let the binary number 'x' have k ones in it. Then $x = \sum_{j=1}^{ j=k} 2^{i_j}$.
$x \, mod 3 = \sum_{j=1}^{ j=k} (-1)^{i_j}$.
However we want this to be 0 mod 3. Then can you figure out the constraint on $i_j$s?