Question

Show that every nondeterministic finite-state automaton is equivalent to another such automaton that has the property that its starting state is never revisited.

Short answer

It is demonstrated that every nondeterministic finite-state automaton is identical to another such automaton whose starting state is never revisited.

Step-by-step solution

General form

Finite-state automaton (Definition): A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs I, a transition function f that assigns a subsequent state to each pair of states and inputs (such that \({\bf{f:S \times I}} \to {\bf{S}}\)), and a subset F of S made up of final states (or accepting states).

Regular expressions (Definition): A recursive definition of the regular expressions over a set I is as follows:

a regular expression with the symbol \(\emptyset \);

a regular expression with the symbol \({\bf{\lambda }}\);

whenever \({\bf{x}} \in {\bf{I}}\); the symbol x is a regular expression.

When A and B are regular expressions, the symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are also regular expressions.

Regular sets are the sets that regular expressions represent.

Theorem 2: If and only if it is a regular set, a set is produced by a regular grammar.

Rules of regular expression represents a set:

\(\emptyset \)represents the string-free set, or the empty set;

\({\bf{\lambda }}\)represents the set \(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

The string having the symbol xin it is represented by the set \(\left\{ {\bf{x}} \right\}\);

(AB) depicts the order of the sets that are represented by both Aand B;

The combination of the sets that bothAand Brepresent is represented by \(\left( {{\bf{A}} \cup {\bf{B}}} \right)\);

The Kleene closure of the sets that Arepresents is represented by \({\bf{A*}}\).

Step 2: Proof of the given statement

Given that, every nondeterministic finite-state automaton is equivalent to another such automaton that has the property that its starting state is never revisited.

To prove: Each nondeterministic finite-state automata is equal to a different automaton of the same type with the characteristic that it never returns to its initial state.

Proof:

Let \({\bf{M}}\) be a nondeterministic finite state that lacks the characteristic of never returning to its initial state. Let \({{\bf{s}}_0}\) represent \({\bf{M}}\)'s initial state.

Assume that \({\bf{M'}}\) is a different nondeterministic finite state that is the nondeterministic finite state M plus a new state \({\bf{s}}_0^\prime \) (but \({{\bf{s}}_0}\) remains the start state).

When \({{\bf{s}}_0}\) is concluded, \({\bf{s}}_0^\prime \) also ends.

All transitions from \({{\bf{s}}_{\bf{i}}} \to {{\bf{s}}_0}\) are switched to \({\bf{s}}_0^\prime \) and are then given the label transitions from \({{\bf{s}}_{\bf{i}}} \to {\bf{s}}_{\bf{0}}^{\bf{'}}\).

As a result of all transitions that would have brought us back to the initial state being shifted to the new state \({\bf{s}}_0^\prime \) instead, \({\bf{M'}}\)has the property that its initial state is never visited.

Additionally, \({\bf{M}}\) and \({\bf{M'}}\) are equal since \({\bf{s}}_0^\prime \) plays the same role in each of them as \({{\bf{s}}_0}\)does in \({\bf{M}}\).

As a result, \({\bf{M'}}\) is the equivalent nondeterministic finite-state automaton of \({\bf{M}}\) with the characteristic that it never returns to its initial state.

Hence, the statement is proved as true.