Question

a)Show that if Mis a finite-state automaton, then the quotient automaton Mrecognizes the same language as M.

b)Show that if Mis a finite-state automaton with the property that for every state of Mthere is a string x∈I∗such that f (s0, x)=s, then the quotient automaton has the minimum number of states of any finite-state automaton equivalent to M.

Short answer

1. M and \(\overline {\bf{M}} \)accepts the same language.
2. If M has the property \({\bf{f(}}{{\bf{s}}_{\bf{o}}}{\bf{,x) = s}}\)for all states s and some string\({\bf{x}} \in {\bf{I*}}\), then \(\overline {\bf{M}} \)has the minimum number of states of all finite state automaton equivalents to M.

Step-by-step solution

Define given

Given \({{\bf{R}}_{\bf{k}}}\)be the relation on the set Sof states of Msuch that\({\bf{s}}{{\bf{R}}_{\bf{k}}}{\bf{t}}\)if and only if for every input string xwith\({\bf{l}}\left( {\bf{x}} \right) \le {\bf{k}}\), where \({\bf{l}}\left( {\bf{x}} \right)\)is the length of string x.

The quotient automatonMof the deterministic finite-state automaton \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\)is the finite-state automaton.

\(\overline {\bf{M}} {\bf{ = (}}\overline {\bf{S}} {\bf{,I,}}\overline {\left\{ {{\bf{f,}}} \right\}} {\bf{(}}{{\bf{s}}_{\bf{o}}}{\bf{)}}{{\bf{R}}_{\bf{*}}}{\bf{,F)}}\), where the set of states S is 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 \(\overline {\bf{M}} \)and input symbols \({\bf{a}} \in {\bf{I}}\), and F is the set consisting of \({{\bf{R}}_{\bf{*}}}\)- equivalence classes of final states of M.

Show that M and \(\overline {\bf{M}} \)accept the same language

Let x be a string that is accepted by M and let \({{\bf{s}}_{\bf{x}}}\)be the state where the string ends in x.

Since x is accepted by M, \({{\bf{s}}_{\bf{x}}}\)is a final state.

By construction of\(\overline {\bf{M}} \), the input x will end at the state\(\left( {{{\bf{s}}_{\bf{x}}}} \right){{\bf{R}}_{\bf{*}}}\). Moreover \(\left( {{{\bf{s}}_{\bf{x}}}} \right){{\bf{R}}_{\bf{*}}}\)is a final state as all-state in\(\left( {{{\bf{s}}_{\bf{x}}}} \right){{\bf{R}}_{\bf{*}}}\) is the final state.

This implies that M and \(\overline {\bf{M}} \) accepts the same language.

Show that \(\overline {\bf{M}} \) has the minimum number of states of all finite state automatons is equivalent to M.

Let’s assume that \({\bf{f(}}{{\bf{s}}_{\bf{o}}}{\bf{,x) = s}}\)for all states s and all strings\({\bf{x}} \in {\bf{I*}}\).

Let N be a finite-state automaton equivalent to M that has the minimum number of states. Since N has the minimum number of states\(\overline {\bf{N}} {\bf{ = N}}\).

Since \(\overline {\bf{N}} \)recognizes the same language as \(\overline {\bf{M}} \) and since they both equivalence as their states, the states \(\overline {\bf{N}} \)need to form a refinement of the state of\(\overline {\bf{M}} \).

Since, \({\bf{f(}}{{\bf{s}}_{\bf{o}}}{\bf{,x) = s}}\)for all s and all strings\({\bf{x}} \in {\bf{I*}}\), there are no empty equivalence classes in \(\overline {\bf{M}} \) and thus the states of \(\overline {\bf{M}} \) the need to form a refinement of the state of\(\overline {\bf{N}} \).

This implies that \(\overline {\bf{M}} \) has the minimum number of states of all finite state automaton is equivalent to M.