GATE CS 2004 Q86 — Regular Expressions and Finite Automata

To determine the language accepted by the given finite state machine (FSM), we can analyze its state transitions based on the number of $1$s and $0$s in the input string.

A standard product automaton for tracking the count of two independent properties modulo $m$ and $n$ has $m \times n$ states. Here, the FSM has $6$ states, which suggests a combination of modulo $3$ and modulo $2$ counters ($3 \times 2 = 6$ states).

Step-by-Step Analysis:

1. Tracking $1$s (Modulo 3): The transitions for input $1$ form cycles of length $3$. This tracks the number of $1$s modulo $3$: $$\text{No. of 1's} \pmod 3 \in \{0, 1, 2\}$$
2. Tracking $0$s (Modulo 2): The transitions for input $0$ form cycles of length $2$. This tracks the number of $0$s modulo $2$: $$\text{No. of 0's} \pmod 2 \in \{0, 1\}$$
3. Accepting State: The start state is also the only accepting (final) state. This state corresponds to the remainder being $0$ for both counts: $$\text{No. of 1's} \equiv 0 \pmod 3 \implies \text{divisible by 3}$$ $$\text{No. of 0's} \equiv 0 \pmod 2 \implies \text{divisible by 2}$$

Thus, the FSM accepts all binary strings where the number of $1$s is divisible by $3$ and the number of $0$s is divisible by $2$.