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.