edited by
12,797 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$
edited by

5 Answers

Best answer
36 votes
36 votes

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

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

4 votes
4 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

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

24 votes
24 votes
2 answers
2
Kathleen asked Oct 9, 2014
7,491 views
Booth’s algorithm for integer multiplication gives worst performance when the multiplier pattern is$101010\ldots1010$$100000\ldots 0001$$111111\ldots 1111$$011111\ldots...
38 votes
38 votes
2 answers
3
Kathleen asked Oct 9, 2014
9,809 views
A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ bytes. The disk is used as follows:$$\begin{array}{|l|}\hline \te...
43 votes
43 votes
5 answers
4