Dark Mode

9,871 views

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

- $4$
- $3$
- $2$
- $1$

22

35 votes

Best answer

2

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

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.

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

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

4

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