GATE CSE 1996 | Question: 2.23

Question

Consider the following state table for a sequential machine. The number of states in the minimized machine will be

$$\begin{array}{|l|l|ll|}\hline \text{} & \text{} & \textbf{Input}\\\hline && \text{0} & \text{1} \\\hline  \textbf{Present State} & \textbf{A} & \text{D,0} & \text{B,1} \\   \text{} & \textbf{B} & \text{A,0} & \text{C,1}\\   & \textbf{C} & \text{A,0} & \text{B,1} \\  \text{} & \textbf{D} & \text{A,1} & \text{C,1} \\\hline \text{} & \text{} & \textbf{Next state, Output}\\\hline \end{array}$$

• A. $4$
• B. $3$
• C. $2$
• D. $1$

Comments

Sir, How B and C are behaving exactly the same on X=1?

---

see the table, and draw the DFA

B

A, 0

C, 1

C

A, 0

B, 1

so both B and C goes to either C or B state , so that means these two different states  behave exactly the same on all the input. That's why they are combined.

---

May be a useful text👇 to read.

State Minimization: Completely Specified Machines

Answer 1

Option B

Minimized Mealy machine will have 3 states as state B & C and be merged because they have same incoming and outgoing transitions. 

For learning minimization of Mealy machine refer to this video. 

https://www.youtube.com/watch?v=oDyz5yUFas4

For learning minimization of Moore machine refer to this video. (from 0:55 onwards)

https://www.youtube.com/watch?v=5shSTtOJrGo