in Digital Logic edited by
9,871 views
40 votes
40 votes

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$
in Digital Logic edited by
9.9k views

4 Comments

Sir, How B and C are behaving exactly the same on X=1?
1
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.

22
22

May be a useful text👇 to read.

State Minimization: Completely Specified Machines

0
0

5 Answers

35 votes
35 votes
Best answer

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

edited by
by

4 Comments

4
4
how do we apply the equivalence method of minimising a FA without knowing the final and non final states?
2
2
0
0
35 votes
35 votes

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

3 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.
2
2
Without indicating initial and final state, is it possible to represent a DFA?
1
1

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

4
4
3 votes
3 votes

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

1 comment

helpful!
0
0
0 votes
0 votes

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

Answer:

Related questions