Question

Let \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) be a deterministic finite-state automaton. Show that the language recognized by \({\bf{M,L}}\left( {\bf{M}} \right)\), is infinite if and only if there is a word x recognized by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\).

Short answer

\({\bf{L}}\left( {\bf{M}} \right)\)is infinite if and only if there is a word x recognized by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\) is proved as true.

Step-by-step solution

General form

Finite-state automaton (Definition): A finite-state automata \({\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 future state to each pair of state and input (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:

The symbol \(\emptyset \) is a regular expression;

The symbol \({\bf{\lambda }}\) is a regular expression;

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

If A and B are regular expressions, then \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are as well.

Regular sets are the sets that regular expressions represent.

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

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 set "x" stands in for the string that contains the symbol x;

(AB) shows how the sets that both Aand Brepresent are arranged;

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

\({\bf{A*}}\) represents the Kleene closure of the sets that Arepresents.

Step 2: Proof of the given statement

Given that, \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) be a deterministic finite-state automaton and \({\bf{L}}\left( {\bf{M}} \right)\) is language recognized by \({\bf{M}}\).

To prove: \({\bf{L}}\left( {\bf{M}} \right)\) is infinite if and only if there is a word x recognized by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\).

Proof:

By demonstrating that there is a word x that is recognised by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\) when \({\bf{L}}\left( {\bf{M}} \right)\) is infinite and by demonstrating that \({\bf{L}}\left( {\bf{M}} \right)\) is infinite when there is a word x that is recognised by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\), we will demonstrate that "\({\bf{L}}\left( {\bf{M}} \right)\)is infinite if and only if there is a wordx that is recognised by M with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\)."

Case (1):

\({\bf{L}}\left( {\bf{M}} \right)\)should be infinite.

Assume that S is finite and \(\left| {\bf{S}} \right|{\bf{ = n}}\).

There are only a finite number of words x with the attribute \({\bf{l}}\left( {\bf{x}} \right){\bf{ < n}}\) because S is infinite (because there are \({{\bf{n}}^{\bf{k}}}\) words with length \({\bf{l}}\left( {\bf{x}} \right){\bf{ = k}}\)).

However, since \({\bf{L}}\left( {\bf{M}} \right)\) is infinite, words of at least n characters exist in \({\bf{L}}\left( {\bf{M}} \right)\), suggesting that there is a word x that M can identify \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\).

Case (2):

Suppose there is a word x that M recognises with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\).

Since M only has S states, when x is the input, at least one state \({{\bf{s}}_{\bf{i}}}\) must be visited twice. Let denote a string of length that terminates in the state \({{\bf{s}}_{\bf{i}}}\) and where denotes the portion of the string that results in the loop (the revisiting of the state).

Lety be the string such that .

Then we remark that \({\bf{L}}\left( {\bf{M}} \right)\) contains all strings .

\({\bf{L}}\left( {\bf{M}} \right)\)is infinite because there exists an endless number of strings with the form .

Hence, the statement is proved as true.