ISRO EC 2025 Q.40: solution and answer

Official answer: CSource: ISRO's final answer key of 15 May 2026

1. The output is $1$ on a '1' input that is at least the second '1' of a run of 1s, where that run came directly after two or more 0s. So the machine must remember how many 0s it has just seen (none, one, or two or more) and whether it is already inside a qualifying run of 1s.

2. Define states: $S_0$ = no useful 0s seen (start, or after a 1 that did not follow two 0s); $S_1$ = exactly one 0 seen; $S_2$ = two or more 0s seen; $S_3$ = at least one 1 seen right after $S_2$ (inside a qualifying run).

3. Transitions, written as next state / output for input 0 and input 1: $S_0$: $0\to S_1/0$, $1\to S_0/0$. $S_1$: $0\to S_2/0$, $1\to S_0/0$. $S_2$: $0\to S_2/0$, $1\to S_3/0$. $S_3$: $0\to S_1/0$, $1\to S_3/1$.

4. The first 1 after the zeros gives output 0 (only one 1 so far). Every later 1 in the run gives output 1. The state after exactly one such 1 and the state after two or more such 1s behave identically (on 1 they give output 1 and stay in the run; on 0 they give output 0 and go to $S_1$), so they merge into the single state $S_3$. No more than these four states are needed.

5. No two of the four states can be merged. $S_3$ is the only state that outputs 1 on input 1, so it differs from every other state. $S_2$ and $S_1$ are told apart by the input sequence $1,1$: from $S_2$ the outputs are $0,1$, from $S_1$ they are $0,0$. $S_0$ and $S_1$ are told apart by $0,1,1$: from $S_1$ the outputs are $0,0,1$, from $S_0$ they are $0,0,0$. $S_0$ and $S_2$ are told apart by $1,1$: from $S_2$ the outputs are $0,1$, from $S_0$ they are $0,0$.

6. All four states are pairwise distinguishable, so the minimum number of states is $4$.