GATE CSE 2007 | Question: 29

Question

A minimum state deterministic finite automaton accepting the language

$L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$   has

• A. $15$ states
• B. $11$ states
• C. $10$ states
• D. $9$ states

Comments

https://gateoverflow.in/blog/8795/minimal-deterministic-finite-automata

Answer 1

Answer will be (A) $15$ states.

We need a separate state for #$0 = 0, 1, 2$ and #$1 = 0, 1, 2, 3, 4$ giving total minimum number of states $= 3 * 5 = 15. $

This is a direct consequence of Myhill-Nerode theorem.

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

Comments

@Arjun Sir, So this is a cross product between 2 DFAs "number of 0 ...." and "number of 1 ...."
My question is..... Do we always get minimal DFA after cross product or we need to check if it can be minimized?

---

for divisble by 2 and 4 , cross product give 8 but it can be made by only 4 states ..(lcm of 2,4)

---

Yes,
-> divisible by 2 and 4 is clear and direct.. 4 is direct multiple.
-> divisible by 3 and 4 is direct.... they are relatively prime to each other

But if question will be like divisible by 12 and 8...   Whats the answer here?
Do we need to check if it can be minimized or answer is 12*8?

---

its lcm only ...24 , not 96 , thats why i wrote lcm(2,4 )

---

but careful its length of w , which is divsible by x and y number ... for symbol its not case 

https://gateoverflow.in/723/gate2001-2-5

---

@sid1221 if,L={w∣w∈{0,1}^∗, number of 0s and 1s in w are divisible by 2 and 4, respectively} Can you show how can we create the finite state machine accepting it in 4 states as per the method of lcm(2,4) ??

---

@sid1221 

its lcm only ...24 , not 96 , thats why i wrote lcm(2,4 )

but careful its length of w , which is divsible by x and y number ... for symbol its not case

Can you please explain it in more detail. I am not getting what you are telling about the symbol.

---

I don't think this lcm is going to work here. question is asking about number of a's divisible by 3 and number of b's divisible by 5. here number of states according to myhill nerode will be number of remainders for 3 * number of remainders of 5. Similarly if it would have been 2,4 it has to be 8. for 2 {0,1} * for 4 {0,1,2,3} and our final state is {0,0} and total states = 8.

@Ahwan @Arjun sir please help if approach is correct.

---

@sid1221 and @Ahwan so when we use lcm and when we use multiplication, is there any specific case .??

---

for divisble by 2 and 4 , cross product give 8 but it can be made by only 4 states ..(lcm of 2,4)

States in DFA for counting a,b is nothing but all possible combinations of their remainders. I don't think LCM has to do anything with this.

@Shaik Masthan @Ayush Upadhyaya plz correct if wrong.

---

yes, you are correct !

those are different data items ( i mean one is defined for a and another is defined for b ) ==> directly multiply !

---

@AHWAN  length of string    and      no. of 'a' & 'b' both are different case .

in case of length of string divisible by 2 and 4 we take L.C.M and we get 4.

IN CASE of no. of 'a' divisible by 2 and no. 'b' divisible by 4  we take multiply and we get 8.

---

If Anyone came up with the answer 9. That's valid if the question is for divisible by 3 OR divisible by 5

---

No,  No.of states remains same even in case of ‘OR’. Only final states will be changed in ‘OR’ case.

Refer this discussion

https://gateoverflow.in/723/gate2001-2-5

 

Answer 2

total states will be 15

 

Answer 3

Given that number of 0's and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15.

As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required) , so product automata will require (3 × 5=15 states).

Comments

Wrong logic 3 0's are also accepted which is not divisible by 15. LCM logic is not required in this question.

Answer 4

Most of the times the answer the answer for number of states  is cartesian product one dfa going horizontally and the other one vertically