Question

One important technique used to prove that certain sets are not regular is the pumping lemma. The pumping lemma states that if \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) is a deterministic finite-state automaton and if x is a string in \({\bf{L}}\left( {\bf{M}} \right)\), the language recognized by M, with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\), then there are strings u, v, and w in \({\bf{I*}}\) such that \({\bf{x = uvw,l}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|\) and \({\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}\), and \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)\) for \({\bf{i = 0,1,2,}}...\). Prove the pumping lemma. (Hint: Use the same idea as was used in Example 5.)

Short answer

Therefore, x is a string in \({\bf{L}}\left( {\bf{M}} \right)\), the language recognized by M, with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\), then there are strings u, v, and w in \({\bf{I*}}\) such that \({\bf{x = uvw,l}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|\) and \({\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}\), and \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)\) for \({\bf{i = 0,1,2,}}...\) 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 subsequent state to each pair of the starting and input states (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;

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: A set is formed by a regular grammar if and only if it is a regular 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 string having the symbolxin 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 both A and B represent is represented by \(\left( {{\bf{A}} \cup {\bf{B}}} \right)\);

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

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: if x is a string in \({\bf{L}}\left( {\bf{M}} \right)\), the language recognized by M, with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\), then there are strings u, v, and w in \({\bf{I*}}\) such that \({\bf{x = uvw,l}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|\) and \({\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}\), and \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)\) for \({\bf{i = 0,1,2,}}...\).

Proof:

Suppose x is a string in \({\bf{L}}\left( {\bf{M}} \right)\) with \({\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|\).

Let's label the states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{{{\bf{i}}_{\bf{1}}}}}{\bf{,}}{{\bf{s}}_{{{\bf{i}}_{\bf{2}}}}}{\bf{,}}...{\bf{,}}{{\bf{s}}_{{{\bf{i}}_{\bf{n}}}}}\), that are met on the input x in M, such that \({\bf{n = l}}\left( {\bf{x}} \right)\).

Since there are \({\bf{n}} \ge \left| {\bf{S}} \right|\) states, at least one of them (state \({{\bf{s}}_{\bf{x}}}\)) gets visited twice on input x (we will choose the first such state). Let \({{\bf{s}}_{\bf{x}}}\) represent the states \({{\bf{s}}_{{{\bf{i}}_{\bf{a}}}}}\) and \({{\bf{s}}_{{{\bf{i}}_{\bf{b}}}}}\) in the input x's state sequence.

Let v represent the part of x which moves the machine from \({{\bf{s}}_{{{\bf{i}}_{\bf{a}}}}}\)to \({{\bf{s}}_{{{\bf{i}}_{\bf{b}}}}}\) in M.

Let u represent the part of x which moves the machine from \({{\bf{s}}_0}\)to \({{\bf{s}}_{{{\bf{i}}_{\bf{a}}}}}\) in M.

Let w represent the part of x which moves the machine from \({{\bf{s}}_{{{\bf{i}}_{\bf{b}}}}}\)to \({{\bf{s}}_{{{\bf{i}}_{\bf{n}}}}}\) in M.

It is observed that \({\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}\) is the same state that is visited twice, with \({{\bf{s}}_{{{\bf{i}}_{\bf{a}}}}}\)and \({{\bf{s}}_{{{\bf{i}}_{\bf{b}}}}}\)being the same state. In addition, \({\bf{l}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|\) because neither u nor v include loops (Since we choose the initial repeating state).

Since x also finishes in the state sin for a positive integer i and since v is a repeating loop in M, the string \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}}\) must also be allowed. The string \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}}\) terminates in the state sin for a positive integer i.

Hence, the statement is proved as true.