Question

Show that \(\left\{ {{{\bf{0}}^{{{\bf{2}}^{\bf{n}}}}}\mid {\bf{n}} \in {\bf{N}}} \right\}\) is not regular. You may use the pumping lemma given in Exercise \(22\) of Section \({\bf{13}}.{\bf{4}}\).

Short answer

Prove \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is not regular by using a proof by contradiction.

Step-by-step solution

Definition

Pumping lemma: If \(x\) is a string in \(L(M)\) with \(L{\rm{(}}x{\rm{)}} \ge |S|\), then there are strings \(u,{\bf{ }}v\) and \(w\) in \({I^*}\) such that \(x = u,v,w\), \(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(M)=\) Language recognized by \(M\)

To proof: \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is not regular

PROOF BY CONTRADICTION

Let us assume, for the sake of contradiction, that \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is regular.

Since \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is regular, there exists some deterministic finite-state automaton \(M = \left( {S,I,f,{s_0},F} \right)\) that generates \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\).

Let \(k = \left| S \right|\). Let us consider the string \(x = {0^{{2^k}}}\).

\(\begin{array}{c}l\left( {{0^{{2^k}}}} \right) = {2^k} \ge 2k\\ = 2|S| \ge |S|\end{array}\)

Using the pumping lemma

By the pumping lemma, there then exist strings \(u,v\) and \(w\) in \({I^*}\) such that \(x = uvw,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 \).

Let \(v\) consist of \(m\) zeros with \(m\) a positive integer, thus \(v = {0^m}\).

However, then \(M\) also generates \({0^{2{\bf{ }}k + p{\bf{ }}m}}\) for all positive integers \(p\) (as \(u{v^i}w \in L{\rm{(}}M{\rm{)}}\)). This then implies that \(2{\bf{ }}k + p{\bf{ }}m\) is a power of \(2\) for all positive integers \(p\).

This is impossible, because the difference between successive powers of \(2\) increases more and more, while the difference between successive terms \(2{\bf{ }}k + p{\bf{ }}m\) increases consistently by \(m\), and thus at some point one of the elements \(2{\bf{ }}k + p{\bf{ }}m\) is not a power of \(2\). Thus, you have derived a contradiction. This then implies that our assumption " \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is regular" is incorrect and thus \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is not regular.

Therefore, the given \(\left\{ {{0^{{2^n}}}\mid n = 0,1,2, \ldots } \right\}\) is not regular.