Monday, November 07, 2005

Algorithm to build DFA's to test divisibility

I found this following algorithm very useful in designing DFA's (especially making DFA's to test the multipules, divisibility etc.....). This logic can help slove may DFA problems lets start with an example and generalize this after that..
Problem: Create a DFA to test the divisibility of a binary string by 3. (Assume the string can be scanned from left to right....ex 11 , 110 )
During the scan of the binary string the current state (Value of the binary string scanned till now) can be in one of the following states
1. 3K 2. 3K+1 3. 3K+2
So if the current state of the DFA is 3K+1 and we scan a '0' the value becomes 2*(3K+1) == 3k+2. If we scan a '1' it becomes 2*(3K+1)+1 == 3K. Similarly if we scan '0' in state '3k+2' it becomes 2*(3k+2) == 6k+4 == 3k+1. So now we have 3 states and move according to the following table.
CURRENT STATE SCAN_LITERAL NEXT_STATE
3k (final state) 1 3k+1
3k (final state) 0 3k
3k+1 1 3k
3k+1 0 3k+2
3k+2 1 3k+2
3k+2 0 3k+1
We can now extened this for the divisibility test for any 'k' that requires a D.F.A of kstates (can we minimize?). With this we can solve problems like the following.
Problem: Design a DFA for the set of string in {0,1,2}* that are ternary(base 3) representations, leading zeros permitted, of numbers that are not multiples of four.
Thought that this would be a useful piece of information.......Cheers Vamsi.

1 comment:

pkr said...

Thanks it really helped me to solve the ternary-problem (from kozens homework-exercises) :-)