Question

Show that the set of palindromes over\(\left\{ {{\bf{0,1}}} \right\}\) is not regular using the pumping lemma given in Exercise 22. (Hint: Consider strings of the form \({{\bf{0}}^{\bf{N}}}{\bf{1}}{{\bf{0}}^{\bf{N}}}\).)

Short answer

The set of palindromes over \(\left\{ {{\bf{0,1}}} \right\}\) is not regular 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;

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 A and 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*}}\).

Pumping lemma: 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,}}...\).

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}}\).

Refer pumping lemma to prove the given statement.

To prove: the set of palindromes over \(\left\{ {{\bf{0,1}}} \right\}\) is not regular.

Proof:

For the sake of contradiction, let's assume that the collection of palindromes over \(\left\{ {{\bf{0,1}}} \right\}\) is regular. We see that a subset of the palindromes is the set \({\bf{A = }}\left\{ {{{\bf{0}}^{\bf{n}}}{\bf{1}}{{\bf{0}}^{\bf{n}}}\left| {{\bf{n}} \in {\bf{N}}} \right.} \right\}\)

Let \({\bf{x = }}{{\bf{0}}^{\bf{k}}}{\bf{1}}{{\bf{0}}^{\bf{k}}}\) and \({\bf{k = }}\left| {\bf{S}} \right|\).

\(\begin{array}{c}{\bf{L}}\left( {\bf{x}} \right){\bf{ = L}}\left( {{{\bf{0}}^{\bf{k}}}{\bf{1}}{{\bf{0}}^{\bf{k}}}} \right)\\{\bf{ = k + 1 + k}}\\{\bf{ = 2k + 1}}\end{array}\)

As a result of the pumping lemma, strings u, v, and w in \({\bf{I*}}\) exist 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,}}...\).

Knowing that\({\bf{L}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|{\bf{ = k}}\), v can only be filled of zeros.

If v is made up entirely of zeroes and \({\bf{l}}\left( {\bf{v}} \right){\bf{ = m}} \ge {\bf{1}}\), then M also generates \({{\bf{0}}^{{\bf{k + m}}}}{\bf{1}}{{\bf{0}}^{\bf{k}}}\) or \({{\bf{0}}^{\bf{k}}}{\bf{1}}{{\bf{0}}^{{\bf{k + m}}}}\) as well (\({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)\)). But neither of these strings is a palindrome, thus v cannot be made up entirely of zeros. Then came to a conflict.

This suggests that our presumption that "the set of palindromes over \(\left\{ {{\bf{0,1}}} \right\}\) is regular" is false and that the set of palindromes over \(\left\{ {{\bf{0,1}}} \right\}\)is therefore not regular.

Hence, the statement is proved as true.