GATE CSE 2025 | Set 1 | Question: 49

Question

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is _______. (Answer in integer).                                                                                                           

$$\overset{\Large{\text{Present state        Next state             Output f}}}{\begin{array}{|c|c|c|c|c|c|} \hline
\text{ $\qquad\qquad\qquad$} & \text{X=0} &  \text{X=1} & \text{X=0} &  \text{X=1}  \\ 
\hline
\text{A} & \text{F} & \text{B} & \text{0} & \text{0}  \\  \hline
\text{B} & \text{D} & \text{C} & \text{0} & \text{0}  \\  \hline
\text{C} & \text{F} & \text{E} & \text{0} & \text{0}  \\  \hline
\text{D} & \text{G} & \text{A} & \text{1} & \text{0}  \\  \hline \text{E} & \text{D} & \text{C} & \text{0} & \text{0}  \\  \hline \text{F} & \text{F} & \text{B} & \text{1} & \text{1}  \\  \hline \text{G} & \text{G} & \text{H} & \text{0} & \text{1}  \\  \hline \text{H} & \text{G} & \text{A} & \text{1} & \text{0}  \\  \hline \end{array}}$$

Comments

minimum no of states is 5

---

https://youtu.be/ZwjbGmItX6Q?si=6V4BIj801PDY6Igw
BY MONALISA mam

Answer 1

Comments

you can give the image to chatgpt and get formated solution in text so you could paste here for neatness. thank you. small suggestion.

---

it is already clear bro

Answer 2

Step 1: Initial Partition by Output

In a Mealy machine, two states can be equivalent only if, for every input symbol, they produce the same output. We group states by their output pairs $(f(0), f(1))$:

• $A, B, C, E$: $(0,0)$  
• $D, H$: $(1,0)$  
• $F$: $(1,1)$  
• $G$: $(0,1)$  

This yields four initial blocks:
$$
P_0 = \big\{ \{A,B,C,E\},\ \{D,H\},\ \{F\},\ \{G\} \big\}.
$$

Step 2: Refinement by Transition Consistency

We refine $P_0$ by checking, for each state, the blocks of its successors under inputs $0$ and $1$.

Block $\{A,B,C,E\}$:  

1.  $A \xrightarrow{0} F,\ A \xrightarrow{1} B$  
2.  $B \xrightarrow{0} D,\ B \xrightarrow{1} C$  
3.  $C \xrightarrow{0} F,\ C \xrightarrow{1} E$  
4.  $E \xrightarrow{0} D,\ E \xrightarrow{1} C$  

  Since $F \in \{F\}$, $D \in \{D,H\}$, and $B,C,E \in \{A,B,C,E\}$, states $A$ and $C$ transition to the same blocks $(\{F\}, \{A,B,C,E\})$, while $B$ and $E$ transition to $(\{D,H\}, \{A,B,C,E\})$. Thus, this block splits into:
  $$
  \{A,C\},\quad \{B,E\}.
  $$

Block $\{D,H\}$:  
 

Both satisfy $D \xrightarrow{0} G,\ D \xrightarrow{1} A$ and $H \xrightarrow{0} G,\ H \xrightarrow{1} A$. Since $G$ and $A$ are uniquely identified in their respective blocks, $D$ and $H$ remain equivalent.Singleton blocks $\{F\}, \{G\}$ cannot be split further.

Thus, the refined partition is:
$$
P_1 = \big\{ \{A,C\},\ \{B,E\},\ \{D,H\},\ \{F\},\ \{G\} \big\}.
$$

No further refinement is possible, as all states within each block have identical output behavior and transition to states in the same blocks.

Step 3: Count Equivalent Classes

The number of equivalence classes in the final partition equals the number of states in the minimal Mealy machine. Hence, the minimal realization requires 5 states

The minimal number of states is summarized in the following table:

$$
\begin{array}{|c|c|}
\hline
\text{Equivalence Class} & \text{States} \\
\hline
1 & A,\ C \\
2 & B,\ E \\
3 & D,\ H \\
4 & F \\
5 & G \\
\hline
\end{array}
$$

Therefore, the minimum number of states required is $\boxed{5}$.

Answer 3

for each row we need to check whether its Next state on X=1, X=0 and O/P on X=1, X=0 are same ,, if same then they can be merged and new state is formed renamed as together . Do this recursively until there is no common  
Note: Don't mistakely take where ever there is 1 in o/p as final state as in dfa and then dont proceed minimizing dfa , its not dfa 

Answer 4

We need to check for same state giving same output and merge them