4,091 views
0 votes
0 votes
Can some plz design a dfa over binary string whr   1. each string is divisible by 7  ?

2. divivsile by 7 but start with 1

3 Answers

Best answer
4 votes
4 votes

A dfa over binary string where

  1. each string is divisible by 7.

L1 = { 0* , 0*1110*, 10101(21) ,.....}  

2. divisible by 7 but start with 1.

L2 = { 111, 1110, 101010*, 1110*, .....}
 

For general case- Div. by n.

http://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n

selected by
1 votes
1 votes

If it means the Decimal Equivalent of the binary string is divisible by 7 :

The logic is quite simple, we need to keep track of the remainders when divided by 7,

0000 mod 7 = 0

0001 mod 7 = 1

0010 mod 7 = 2

0011 mod 7 = 3

0100 mod 7 = 4

0101 mod 7 = 5

0110 mod 7 = 6

0111 mod 7 = 0

1000 mod 7 = 1

1001 mod 7 = 2

1010 mod 7 = 3

1011 mod 7 = 4

1100 mod 7 = 5

1101 mod 7 = 6

1110 mod 7 = 0

Now, draw six states with the first state being the final state. 

0000 must be final state, so there is a self-loop to first state.

0001 must go to state 1 (which symbolically means remainder is 1)

0010 must go to state 2 (which symbolically means remainder is 2)

... Do this for all the above 15 different strings, At the end you will get your DFA.

Here it is :

                              

0 votes
0 votes

If the length of the string is divisible by 7:

1) Each string must be divisible by 7, this means that the strings of length 0, 7, 14, 21,.. are accepted.

Now, we can make a 7 state DFA to accept the language. Since we want the string with length 0 to be accepted, we make the first state as a final state.

Next, we can traverse on the first 6 symbols and make a transition from the 7th to the first state (which we marked as final) so that the string with length 7 gets accepted. 

You can observe that all the strings of length divisible by 7 are accepted.

Here is the DFA.

                            

2) Since the string must start with a 1, there are 2 different paths from the first state. If we encounter a 0 then DFA must go to a dead state.

Else, it must again accept all the strings of length 7.

The DFA is:

                         

edited by

Related questions

1 votes
1 votes
0 answers
3
3 votes
3 votes
0 answers
4
cse23 asked Jan 25, 2017
6,575 views
Which of the following cannot be the intermediate sequence if we apply quick sort on 9,8,7,6,5,4,3,2,1?Assume the pivot is always the first elementA) 1,8,7,6,5,4,3,2,9B) ...