The following finite state machine accepts all those binary strings in which…
2004
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
Attempted by 201 students.
Show answer & explanation
Correct answer: A
Key idea: interpret each state as a pair (r1, r0) where r1 = number of 1's mod 3 and r0 = number of 0's mod 2.
Start and accepting state is (0,0): zero 1's modulo 3 and zero 0's modulo 2.
On input 1: update the first component by adding 1 modulo 3 (r1 := (r1+1) mod 3). This cycles through the three columns in the diagram.
On input 0: toggle the second component (r0 := (r0+1) mod 2). This moves between the two rows in the diagram.
Therefore the automaton accepts exactly those binary strings for which the number of 1's is congruent to 0 modulo 3 (i.e., divisible by 3) and the number of 0's is congruent to 0 modulo 2 (i.e., divisible by 2).
Conclusion: the language is { w in {0,1}* | #1(w) ≡ 0 (mod 3) and #0(w) ≡ 0 (mod 2) }.
A video solution is available for this question — log in and enroll to watch it.