## 4 Answers

Correct Option: **D**

It can be proved using Myhill Nerode theorem. We need a separate state for $\#a \ mod \ 6 = 0..5$ and $\#b \ mod \ 8 = 0..7 $. Each combination of them must also be a new state giving $6*8 = 48$ minimum states required in the DFA.

Reading Myhill-Nerode theorem might be confusing though it is actually very simple.

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

### 14 Comments

L1={w over Σ={a,b} accepting all strings which have number of a's divisible by 6}, say has 'm' states

L2={w over Σ={a,b} accepting all strings which have number of b's divisible by 8}, say has 'n' states

Step 1: Take Cartesian product and create a dfa M with m*n # of states. (total # of states)

Step 2: The difference of AND/OR comes on basis of selection of final states in M..

If OR(means UNION) so in M choose all states as final states wherever final states of EITHER M1 or M2 occurs..

If AND(means INTERSECTION) so in M choose all states as final states wherever final states of BOTH M1 and M2 occurs..

So by question, M1 has 6 states, M2 has 8 states. Final dfa has 6*8=48 states.(only total # of states is asked here and it will be minimum).

Please correct me if I am wrong.

In case if the question had been given as "** number of a's divisible by 6 and number of a's divisible by 8**" then the number of states would be 24 and if given as "** number of a's divisible by 6 but not divisible by 8** " then the number of states would be 24 right?

Moreover if it is given as " **number of a's divisible by 6 and number of b's divisible by 12 **" (or) "** number of a's divisible by 6 or number of b's divisible by 12 **" (or) "** number of a's divisible by 6 but not number of b’s divisible by 12 **" then it would be 72 states right?

Anyone please clarify.

- For different symbols – no. of a’s is divisible by x and no. of b’s is divisible by y, we will have xy states.
- For same symbols – no. of a’s is divisible by x and no. of a’s is divisible by y, we will have lcm(x,y) states.

Instead of “and” there can be any logical operation (or, but not etc) but the no of states will still remain the same, only the set of final states will change.

### 5 Comments

Only final states will be more. We will count final states like (0,x) and (x, 0) where x E [0,5] for 'a' and [0,7] for 'b'.

For 'a' we have 6 such final states, for 'b' we have 8.

Total 6 + 8 - 1 = 13 final states as we have counted state (0,0) twice.

**I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.**

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)

Case 2: Divisible by a or b ------> If a divides b or b divides a then Min. states = GCD(a,b)

### 5 Comments

anyone verify this"

**I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.**

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)

Case 2: Divisible by a or b ------> If a divides b or b divides a then Min. states = GCD(a,b)

"