Question

Show that \(\left\{ {{1^p}\mid p\;\;\;prime} \right\}\} is not regular. You may use the pumping lemma given in Exercise 22 of Section 13.4.

Short answer

It is shown & proved that \(\left\{ {{1^p}\mid p\;\;\;prime} \right\}\} is not regular.

Step-by-step solution

Definition

Pumping lemma: If \(x\} is a string in \(L{\rm{(}}M{\rm{)}}\} with \(L{\rm{(}}x{\rm{)}} \ge |S|\}, then there are strings \(u,v\} and \(w\} in \({I^*}\} such that \(x = uvw,{\bf{ }}L{\rm{(}}uv{\rm{)}} \le |S|\} and \(l{\rm{(}}v{\rm{)}} \ge 1\} and \(u{v^i}w \in L{\rm{(}}M{\rm{)}}\} for \(i = 0,1,2, \ldots \}

Proving by contradiction

Given:

\(M = \left( {S,I,f,{s_0},F} \right)\}is a deterministic finite-state automaton

\(L{\rm{(}}M{\rm{)}} = \}Language recognized by \(M\}

\(P = \left\{ {{1^p}\mid p\;\;\;prime} \right\}\}

To proof: is not regular\(P\}

PROOF BY CONTRADICTION

Let us assume, for the sake of contradiction, that \(P\} is regular.

Since \(P\} is regular, there exists some deterministic finite-state automaton \(M = \left( {S,I,f,{s_0},F} \right)\} that generates \(P\}.

Let \(k = \left| S \right|\}. Let us consider the string \(x = {1^{{p_k}}}\} with \({p_k}^{th}\} \({k^{th}}\} prime.

\(l\left( {{1^{{p_k}}}} \right) \ge l\left( {{1^k}} \right) = k = |S|\}

Using the pumping lemma

By the pumping lemma, there then exist strings \(u,v\} and \(w\} in \({I^*}\} such that \(x = uvw,L(uv) \le |S|\} and \(l(v) \ge 1\} and \(u{v^i}w \in L{\rm{(}}M{\rm{)}}\} for \(i = 0,1,2, \ldots \}

Let \(v\} consist of \(m\} ones with \(m\} a positive integer, thus \(v = {1^m}\}.

However, then \(M\} also generates \({1^{{p_k} + pm}}\} for all positive integers \(p\} (as \(u{v^i}w \in L{\rm{(}}M{\rm{)}}\}). This then implies that \({p_K} + p{\bf{ }}m\} is a prime for all positive integers \(p\}.

This is impossible, because the difference between successive primes increases more and more (as there are \(n - 1\} nonprimes from \(n{\bf{ }}! + 2\} and \(n{\bf{ }}! + n\}), while the difference between successive terms \({p_K} + p{\bf{ }}m\} increases consistently by \(m\}, and thus at some point one of the elements \({p_K} + p{\bf{ }}m\} is not a prime. Thus, you have derived a contradiction.

It implies that the assumption which is " \(P\} is regular" is incorrect.

Hence, \(P\} is not regular.