Question

Showthat there is a nonnegative integer n such that the setof n-equivalence classes of states ofM is the same as the set of \({\bf{(n + 1)}}\)-equivalence classes of states of M. Then show for this integer n, the set of n-equivalence classes of states of M equals the set of∗-equivalence classes ofstates of M.

The quotient automatonMof the deterministic finite-state automaton\({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\)is the finite-state automaton\({\bf{(S,I,f,(}}{{\bf{s}}_{\bf{o}}}{\bf{)}}{{\bf{R}}_{\bf{*}}}{\bf{,F)}}\), where the set of states’Sis the set of∗-equivalence classes of S, the transition function f is defined by \({\bf{f ((s),}}{{\bf{R}}_{\bf{*}}}{\bf{, a) = (f }}\left( {{\bf{s,a}}} \right){\bf{)}}{{\bf{R}}_{\bf{*}}}\)for all states \({\bf{(s)R*}}\)of Mand input symbols \({\bf{a}} \in {\bf{I}}\), and F is the set consisting of \({{\bf{R}}_{\bf{*}}}\)- equivalence classes of final states of M.

Short answer

There exists a non-negative integer n such that n-equivalence classes of M are the same as the \({\bf{n + 1}}\) equivalence classes of M.

The set of n-equivalence classes of M equal the set of ∗-equivalence classes of states of M.

Step-by-step solution

Definition

If a relation R is transitive, symmetric, and reflexive, then it is an equivalence relation.

A relation R on a set A is reflexive if\({\bf{(a,a)}} \in {\bf{R}}\)for every element\({\bf{a}} \in {\bf{A}}\).

If\({\bf{(b,a)}} \in {\bf{R}}\)whenever\({\bf{(a,b)}} \in {\bf{R}}\), a relation R on a set A is said to be symmetrical.

A relation R on a set A is transitive if\({\bf{(a,b)}} \in {\bf{R}}\)and\({\bf{(b,c)}} \in {\bf{R}}\)then\({\bf{(a,c)}} \in {\bf{R}}\).

Show that there exists a non-negative integer n such that n-equivalence classes of M are the same as the n+1 equivalence classes of M.

Let M be a deterministic finite state machine with n state.

Let E be an n equivalence class of M. let a and b be the state in E. \({\bf{a}}{{\bf{R}}_{\bf{n}}}{\bf{b}}\).

By the definition of \({\bf{f}}\left( {{\bf{a,x}}} \right)\) and \({\bf{f}}\left( {{\bf{b,x}}} \right)\) are both final state or both non final state.

Let y be a string with a maximum length of \({\bf{n + 1}}\). \({\bf{a}}{{\bf{R}}_{\bf{k}}}{\bf{b}}\)\({\bf{f}}\left( {{\bf{a,y}}} \right)\) and \({\bf{f}}\left( {{\bf{b,y}}} \right)\) are both final states or both non-final states if y is a string with a length of at most n. Assume that y is an \({\bf{n + 1}}\)-length string.

Since the length of y is greater than the number of state n, there exists a state’s that is visited at least twice then the input is n. Thus, there exists two strings \({{\bf{y}}_{\bf{1}}}\)and \({{\bf{y}}_{\bf{2}}}\)such that \({\bf{y = }}{{\bf{y}}_{\bf{1}}}{{\bf{y}}_{\bf{2}}}\) and such that the string \({{\bf{y}}_{\bf{1}}}\) ends in the same state as the string y.

Since \({{\bf{y}}_{\bf{1}}}\)has length of at most n, \({\bf{f(a,}}{{\bf{y}}_{\bf{1}}}{\bf{)}}\) and \({\bf{f(b,}}{{\bf{y}}_{\bf{1}}}{\bf{)}}\) are both final state or both non final state.Since y and \({{\bf{y}}_{\bf{1}}}\)end in the same state: \({\bf{f}}\left( {{\bf{a,y}}} \right)\) and \({\bf{f}}\left( {{\bf{b,y}}} \right)\) are both final state or both non final state.

Thus \({\bf{f}}\left( {{\bf{a,y}}} \right)\) and \({\bf{f}}\left( {{\bf{b,y}}} \right)\) are both final state or both non final state for every input string y with \({\bf{l(y)}} \le {\bf{n + 1}}\). This implies that \({\bf{a}}{{\bf{R}}_{{\bf{n + 1}}}}{\bf{b}}\) and thus E is a \(\left( {{\bf{n + 1}}} \right)\) equivalence class of M.

Therefore, there exists a non-negative integer n such that n-equivalence classes of M are the same as the \({\bf{n + 1}}\) equivalence classes of M.

The set of n-equivalence classes of M equal the set of ∗-equivalence classes of states of M.