edited by
7,713 views
21 votes
21 votes

Following is a state table for time finite state machine.

$$\begin{array}{|l|ll|}\hline \textbf{Present State}  &  \textbf{Next State Output}  \\ & \textbf{Input- 0} &  \textbf{Input-1} \\\hline  \text{A} & \text{B.1} & \text{H.1} \\  \text{B} & \text{F.1} & \text{D.1} \\ \text{C} & \text{D.0} & \text{E.1} \\ \text{D} & \text{C.0} & \text{F.1} \\ \text{E} & \text{D.1} & \text{C.1} \\ \text{F} & \text{C.1} & \text{C.1} \\ \text{G} & \text{C.1} & \text{D.1} \\ \text{H} & \text{C.0} & \text{A.1} \\\hline \end{array}$$

  1. Find the equivalence partition on the states of the machine.

  2. Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).

edited by

2 Answers

Best answer
30 votes
30 votes

As nothing is mentioned in question, assuming that the first state itself is the start state i.e. State $A$  so, State $G$ is not reachable from the start and hence is removed before applying the minimization algorithm.

  • $P0 \rightarrow [ABEFG] [CDH] \rightarrow [ABEF] [CDH]$
  • $P1 \rightarrow [AB] [EF] [CDH]$
  • $P2 \rightarrow [A] [B]  [EF] [CD] [H]$
  • $P3 \rightarrow [A] [B]  [EF] [CD] [H]$ 
    //$P2==P3$ So, stop

State table for the minimal machine ::

$$\begin{array}{|l|l|l|} \hline \text{Present State} & \text{input = 0} & \text{input = 1} \\\hline \text{A} & \text{B.1} & \text{H.1} \\\hline \text{B} & \text{EF.1} & \text{CD.1} \\\hline \text{CD} & \text{CD.0} & \text{EF.1} \\\hline \text{EF} & \text{CD.1} & \text{CD.1} \\\hline \text{H} & \text{CD.0} & \text{A.1} \\\hline \end{array}$$

edited by

Related questions

24 votes
24 votes
1 answer
1
Kathleen asked Sep 29, 2014
14,264 views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...