GATE CSE 2004 | Question: 86

Question

The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively:

     

• A. divisible by $3$ and $2$

• B. odd and even

• C. even and odd

• D. divisible by $2$ and $3$

Comments

By just traversing and using the elimination method, we can answer this question.

Answer 1

Option (C) and option (D) are cancelled out clearly because with $3$ $1$s we can reach the final state. There is an string where we can reach the final state by $6$ $1$'s now $6$ is nt odd but it is divisivble by $3$. Hence, option (A) is correct.

Comments

why not D?

---

@Pranav Madhani

option d is 1 divisible by 2 and 0 is divisible  3 which is wrong. 

because 

No. of 0's % 2 = 0 

no. of 1's % 3 =0

 

 

Answer 2

ε (Empty string) is accepted here. So option (B) & (C) are canclelled out !

No of 0's % 2 = 0 . So answer => A

Answer 3

No. of 1s is represented horizontally and 0s vertically.

There are 3 states each for number of 1s. So, it is understood that states are for 0, 1 and 2 as remainders when no. of 1s is divided by 3.

Similarly, there are 2 states each for number of 0s. So, it is understood that states are for 0 and 1 as remainders when no. of 0s is divided by 2.

Hence option A is correct.

Comments

What is difference between option A and D?

---

in option (A) number of 1's divisible by 3 and number of 0's divisible  by 2 and

option (D) number of 1's divisible by 2 and number of 0's divisible  by 3

Answer 4

Correct option: A

This is because every string accepted by this DFA has 1’s divisible by 3 and 0’s divisible by 2.

For Example:

1010101011 is accepted by DFA,

Number of 1’s: 6%3=0 (Divisible by 3)

Number of 0’s: 4%2=0 (Divisible by 2)