9,871 views

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}$$

1. $4$
2. $3$
3. $2$
4. $1$

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

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

by

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

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 ^{*}$

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.

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

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

### 1 comment

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