Question

a)Show that sand tare 0-equivalent if and only if either both sand tare final states or neither snor tis a final state. Conclude that each final state of M, which is an R∗-equivalence class, contains only final states of M.

b)Show that if kis a positive integer, then sand tare k-equivalent if and only if sand tare (k−1)-equivalent, and for every input symbol a∈I, f (s, a)and f (t, a)

are (k−1)-equivalent. Conclude that the transition function fis well-defined.

c)Describe a procedure that can be used to construct the quotient automaton of a finite-automaton M.

Short answer

1. \({\bf{s}}{{\bf{R}}_{\bf{o}}}{\bf{t}}\)if and only if s and t are either final states or neither is the final state.
2. If k is a positive integer, then \({\bf{s}}{{\bf{R}}_{\bf{o}}}{\bf{t}}\)if and only is \({\bf{s}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{t}}\)and\({\bf{f(s,a)}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{f(t,a)}}\).
3. Test every pair of states for k-equivalence in M for\({\bf{k = 0,1,2, \ldots }}{\bf{.n}}\), where n represents the smallest integer such that n-equivalence classes are the same as the \({\bf{n - 1}}\) equivalence classes of M.

Step-by-step solution

Given Information

For every input string x with\({\bf{l}}\left( {\bf{x}} \right) \le {\bf{k}}\), where l(x) is the length of the string x,\({\bf{s}}{{\bf{R}}_{\bf{k}}}{\bf{t}}\)if and only if is given as the relation on the set S of states of M.

Show that \({\bf{s}}{{\bf{R}}_{\bf{o}}}{\bf{t}}\) if and only if s and t are either final states or neither is the final state.

Let\({\bf{a}}{{\bf{R}}_{\bf{o}}}{\bf{t}}\). By the definition of \({{\bf{R}}_{\bf{o}}}{\bf{: f}}\left( {{\bf{s,x}}} \right)\) and \({\bf{f}}\left( {{\bf{t,x}}} \right)\)are either final states or neither is final state for every input string x with\({\bf{l(x)}} \le 0\).

Thus \({\bf{f(s,\lambda )}}\)and \({\bf{f(t,\lambda )}}\) are either final states or neither is a final state as \({\bf{\lambda }}\) is the only string of length 0.

Let s and t are both final states or neither is the final state.

Then implies that \({\bf{f(s,\lambda )}}\)and \({\bf{f(t,\lambda )}}\) are either final states or neither is the final state, as \({\bf{f(s,\lambda ) = s}}\)and\({\bf{f(t,\lambda ) = t}}\), s and t either final state or neither is the final state

If k is a positive integer, \({\bf{s}}{{\bf{R}}_{\bf{o}}}{\bf{t}}\)then if and only is \({\bf{s}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{t}}\)and\({\bf{f(s,a)}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{f(t,a)}}\)

Let k be a positive integer.

If \({\bf{s}}{{\bf{R}}_{\bf{k}}}{\bf{t}}\)then \({\bf{f}}\left( {{\bf{s,x}}} \right)\) and \({\bf{f}}\left( {{\bf{t,x}}} \right)\) are either final states or neither is final state for every input string x with\({\bf{l(x)}} \le {\bf{k}}\). Let y be an input string of length \({\bf{k - 1}}\) and let\({\bf{a}} \in {\bf{I}}\).

Since y is also an input string of length at most\({\bf{s}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{t}}\). Since ya is a string of length at most \({\bf{k:f(s,a)}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{f(t,a)}}\)as \({\bf{(s,ay) = f(f(s,a),y)}}\)and\({\bf{f(t,ay) = f(f(t,a),y)}}\).

If\({\bf{s}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{t}}\)and\({\bf{f(s,a)}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{f(t,a)}}\) are either final states or neither is final state for every input string x with \({\bf{l(x)}} \le {\bf{k}} - 1\)and \({\bf{f(s,xa)}}\)and \({\bf{f(t,xa)}}\)are either final state or neither is final state for every input string x with\({\bf{l(x)}} \le {\bf{k}} - 1\) are either final states or neither is final state for every input string x with\({\bf{l(x)}} \le {\bf{k}} - 1\).

Let y be an input string of length k is the y has length \({\bf{k - 1}}\) then \({\bf{f}}\left( {{\bf{s,x}}} \right)\) and \({\bf{f}}\left( {{\bf{t,x}}} \right)\) are either final states or neither is the final state as\({\bf{s}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{t}}\). If y has length k, then \({\bf{y = za}}\) with \({\bf{l(}}z{\bf{)}} \le {\bf{k}} - 1\) and \({\bf{z}} \in {\bf{I*}}\), while\({\bf{f(s,xa)}}\)and \({\bf{f(t,xa)}}\)are either final states or neither are final states\({\bf{f(s,a)}}{{\bf{R}}_{{\bf{k - 1}}}}{\bf{f(t,a)}}\).

Show the finite automaton.

Test every pair of states for k-equivalence in M for\({\bf{k = 0,1,2, \ldots }}{\bf{.n}}\), where n represents the smallest integer such that n-equivalence classes are the same as the \({\bf{n - 1}}\) equivalence classes of M and thus I stop determining the equivalence classes when I obtain the same equivalence as for the value of k.

Thus, the n-equivalence classes of M are then the state\({\bf{M*}}\).