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

$3$ states are required in the minimized machine. States $B$ and $C$ can be combined as follows:

Comments

how do we apply the equivalence method of minimising a FA without knowing the final and non final states?

---

@Abhineet Singh

https://youtu.be/dV-9bsJZwF0  

 

---

If we draw DFA then we can easily observe that  B & C are just oscillating on 1 without changing output i.e. 1/1 & also on 0 B&C are behaving in same manner i.e. 0/0 so we can easily merge B & C.

Answer 2

If we make DFA from above table we get DFA like below.

Now as shown in below img (LHS) State B&C are equal so they can make one state (B) as shown in RHS.

Hence Option B (3 states in MFA is Ans).

Q:-> Why B & C are equal??

Ans:->

B -> 1/1 -> C

C-> 1/1  -> B

B,C-> 0/0 -> A

Two states p,q are equal if $\delta (p,x)=\delta (q,x) => \forall  x    \epsilon  \sum ^{*}$

Comments

could the approach of solving this ques be, that, combine every possible pair of states first and if                    their transition on the same input leads to same state with same output. like, B and C on 0 both goes to A, and on 1 goes to same state (BC) which is formed by combining them, then they are equal.

in the next step we can try checking bigger combinations like which other state may join with BC, in similar fashion.

what do you say about this approach.

---

Without indicating initial and final state, is it possible to represent a DFA?

---

DFA without final state is Mealy and Moore Machine which does not act as language acceptors but act as a transducer.

see this for more-

https://stackoverflow.com/questions/21731715/dfa-without-final-state

https://cs.stackexchange.com/questions/82334/are-finite-state-transducers-and-mealy-machines-the-same-machines

Answer 3

While minimizing DFA’s we write 1-equivalent based on final and non final states i.e we group final states and non final states separately.

But in melay machine we don’t have final state, so we write 1-equivalent based on output produced on transitions.

If we observe the table, the states {A,B,C} on seeing input 0 goes to some other state producing output 0, similarly these states on 1 produces output 1 therefore in 1-equivalent we make A,B,C as a group.

Similarly state D on input 0 produces 1 and input 1 produces 1, and D is only state producing such output therefore we put D in another group.

{A,B,C}  {D}  – 1-equivalent

{A} {B,C} {D} – 2-equivalent,  we found it similar to finding 2-equivalent in DFA minimization

{A} {B,C} {D} – 3-equivalent 

Therefore we combine B,C states

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

Comments

helpful!

Answer 4

plz rotate to see it correctly, in the end as you can see three equivalence classes are made so there will be three states in minimized finite state machine