Question

Answer these questions about the finite-state automaton shown here.

a)Find the k-equivalence classes of M for\({\bf{k = 0,1,2, and 3}}\). Also, find the∗-equivalence classes of M.

b)Construct the quotient automaton M of\(\overline {\bf{M}} \).

Short answer

1. The states for 1-equivalence class.

   Final states=\({{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}{\bf{,}}{{\bf{s}}_{\bf{6}}}\)

   Non-final state=\({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\).

   
   
2. Construction:

Step-by-step solution

According to the figure

Here the given figure contains three states\({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}\).

If there is an arrow from \({{\bf{s}}_{\bf{i}}}\) to \({{\bf{s}}_{\bf{j}}}\) with label x, then we write it down in a row \({{\bf{s}}_{\bf{j}}}\)and in the row \({{\bf{s}}_{\bf{i}}}\)and in column x of the following table.

State	0	1
\({{\bf{s}}_{\bf{o}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{4}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{6}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{4}}}\)
\({{\bf{s}}_{\bf{4}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{6}}}\)
\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{4}}}\)
\({{\bf{s}}_{\bf{6}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{6}}}\)

0-equivalence class:

The 0-equivalence class are the set of all final state and the set of all non-final states. The final states are denoted by two circles, while the non-final states are denoted by a single circle.

Final states=\({{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}{\bf{,}}{{\bf{s}}_{\bf{6}}}\) and non-final state=\({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\).

1-equivalence class

S and t are in the same 1-equivalence class, if s and t are both non-final or are both final states and if I arrive at both final states and both non-finite states, when the input is a and when starting from states’s and t.

\({{\bf{s}}_{\bf{o}}}\)are the only non-final states that move to a non-final state when the input is 0, thus \({{\bf{s}}_{\bf{o}}}\)is in its 1-equivalence class.

\({{\bf{s}}_{\bf{1}}}\)is the only remaining non-final state that moves to a non-final state when the input is 1, thus \({{\bf{s}}_{\bf{1}}}\)is in its 1-equivalence class.

\({{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\)is the only remaining non-final state that moves to a non-final state when the input is 0 and 1, thus\({{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\)is in the same 1-equivalence class.

\({{\bf{s}}_{\bf{6}}}\)is the only remaining final state that remains at a final state when the input is 1, thus\({{\bf{s}}_{\bf{6}}}\)is in its 1-equivalence class.

\({{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}\)are the remaining final states that move to a final state when the input is 0 and that move to a non-final state when the input is 1, thus\({{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\)being in the same 1-equivalence class.

2-equivalence class:

The 1-equivalence classes that contain only a single state are also 2-equivalence classes.

\({{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\)are in the same 1-equivalence class. The input01 ends at a non-final state when starting from\({{\bf{s}}_{\bf{2}}}\), while the inputs 00, 10, 11 ends at a final state when starting from\({{\bf{s}}_{\bf{2}}}\). Input 01 ends at a non-final state when starting from\({{\bf{s}}_{\bf{4}}}\), while input 00, 10, 11 ends at a final state when starting from\({{\bf{s}}_{\bf{4}}}\). Thus \({{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\)are also in the same 2-equivalence class.

\({{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}\)are in the same 1-equivalence class. Input 01 ends at a non-final state when starting from\({{\bf{s}}_{\bf{3}}}\), while input 00, 10, 11 ends at a final state when starting from\({{\bf{s}}_{\bf{3}}}\). Input 01 ends at a non-final state when starting from\({{\bf{s}}_{\bf{5}}}\), while input 00, 10, 11 ends at a final state when starting from\({{\bf{s}}_{\bf{5}}}\). Thus\({{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}\) are also in the same 2-equivalence class.

3-equivalence class:

The 1-equivalence classes are the same as the 2-equivalence classes and thus the equivalence classes won’t change anymore. This implies that the 3-equivalence classes are also the same as the 1-equivalence classes are same as 2-equivalence classes.

Construction of the quotient automaton M of\(\overline {\bf{M}} \).

The 1-equivalence classes are the same as the 2-equivalence classes in part (a) thus the *-equivalence classes are the same as the 1-equivalence classes.

Thus the 5 states of the quotient automaton\(\overline {\bf{M}} \)are then these equivalence classes, which I place within a circle.

Each and I also draw a second circle when the states are the final state in M.

I draw an arrow from state s and t with label a, when there is an arrow from a state, n the equivalence class of s to the state in the equivalence class to t with label a.