Reduce the number of states in the following state table and

Reduce the number of states in the following state table and tabulate the reduced state table.

Solution

In the above table ,state j is removed because j state is un reachable.

After drawing the state diagram it comes to know that state i and h are final state. From these state we can not go to any other state.

For minimizing the above automata, we will have to make (pi) sets.

first of all make o set. for this, make two set, first set contains final state and second set contains non final states.

o = {{i,h},{a,b,c,d,e,f,g}}

in the above step i partitioned all the state in 2 group, one group is final state group and another one is not final state group. i removed state j as it is unreachable state.

1 ={{i,h},{a,b,c,d},{e,f,g}}

For 1 set , there are two sets in o:

For partitioned second set, consider i and h, the entries corresponding to i and h under 0-column are a and a. these entries belongs to second set.so no problem. similarly i and h under 1-column are c and c. so i and h will present in a single group.

similarly the entries correspoinding to a,b,c,d under 0-column are a,b,e,f of same group of o. a,b,c,d under 1-column are e,f,d,c of same group of o. so present in a single set in 1 set .

same method applies to e,f,g.

2 ={{i,h},{a,b},{c,d},{e,f,g}}

similar procedure applied to 2 set.

3 ={{i,h},{a,b},{c,d},{e,f,g}}

then we get 3 set. we make sets until we find last two sets equal.

in this example, we find 2 = 3 so stop making sets.

Final minimized table is :

                                     next state                                         output

State

x=0

x=1

[a,b]

[a,b]

[e,f,g]

[c,d]

[e,f,g]

[c,d]

[e,f,g]

[e,f,g]

[i,h]

[i,h]

[a,b]

[c,d]

State	x=0	x=1	x=0	x=1
[a,b]	[a,b]	[e,f,g]	0	1
[c,d]	[e,f,g]	[c,d]	1	1
[e,f,g]	[e,f,g]	[i,h]	1	1
[i,h]	[a,b]	[c,d]	0	0