5
$\begingroup$

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} and we need to prove that it is not regular by use of the pumping lemma.

(i.e. L is words whose length is a power of 2: a, aa, aaaa, aaaaaaaa etc.)

I appreciate the concept of the proof so here we go:

Assuming regularity of L and using the Pumping Lemma, we have $ {a^{2^p}} = {xyz}$ where:

a) ${|y| > 0}$

b) ${|xy| \le p}$

c) $xy^iz \in L \ \forall \ i \ge 0$

(also $ |xyz|\ = 2^p \ge p$)

(notice both x and z can be empty)

I choose $ i = 2$ to get $xy^2z$ so (since $y>0$) $|xy^2z| > 2^p$

I understand that the next step is trying to prove that $|xy^2z| < 2^{p+1}$ so that the final result is $2^p < |xy^2z| < 2^{p+1}$ and so $xy^2z$ cannot be an element of L.

However if $|y| = p$ and so $|x| = 0,\ |z| = 0$ then this is not possible as taking $y^2$ is just doubling the length of the word which makes another word that fits the language.

Am I missing something important? I have found proofs on multiple web pages (see below) that just seem to assume y cannot be of length p but as far as I can see this isn't the case.

http://cs.geneseo.edu/~baldwin/csci342/fall2012/0928pump.html http://www.cse.buffalo.edu/courses/cse396/content/hwSol-5.pdf

Thanks very much in advance and please let me know if there is anything I should clarify.

$\endgroup$
4
$\begingroup$

Take a larger $i$. The concept is that gaps between $|2^n|$ get bigger than $|y|$.

$\endgroup$
  • $\begingroup$ Thanks, I did it with $i = 3$ and it worked (both intuitively and on paper). Do you know why all the proofs I have come across used $i = 2$? $\endgroup$ – Chris Nov 15 '13 at 23:12
  • $\begingroup$ To be fair, $i = 2$ is sufficient. The $p$ in $2^p$ is the pumping length - a parameter of a language, not of a word. Because $|xy| \leq p \implies |y| \leq p < 2^p$, repeating $y$ can't double the string. $\endgroup$ – Karolis Juodelė Nov 15 '13 at 23:24
  • $\begingroup$ But if y is the entire string and both x and z are empty, surely doubling y doubles the string? (sorry, I feel I'm really missing something but I just can't get my head around it). $\endgroup$ – Chris Nov 15 '13 at 23:50
  • $\begingroup$ By pumping lemma $|y|$ can't be longer than a certain number $p$. If you wanted to show that for any word of length $2^n \geq p$ pumping lemma fails, you'd have to worry about $2^n = p$, however, you get to choose your string. You can choose it as long as you like, $|y|$ will have the same upper bound. $\endgroup$ – Karolis Juodelė Nov 15 '13 at 23:55
  • $\begingroup$ I'll have to think this over in the morning but I think I see the difference. Thanks very much for all your help. $\endgroup$ – Chris Nov 16 '13 at 0:30
0
$\begingroup$

Let me write down my proof on the question.

We have the language $L = \{a^{2^n} | n≥0\}$ and we assume that $L$ is a regular language.

The pumping lemma states that there exists $p \in \mathbb{N}$ such that every string $w\in L$ of length at least $p$ can be written as $w = xyz$, satisfying the following conditions:

  1. $|y| ≥ 1$
  2. $|xy| ≤ p$
  3. $\forall i ≥ 0, xy^iz \in\! L$

Lets consider the string $w=a^{2^p}, |w|= 2^{p}\geq p$. According to the pumping lemma $w$ can written in the form $xyz$, with $|x|=a^n$, $|y|=a^m$ and $|z|=a^l$. Moreover $xy^iz\!\in \! L\;\forall i\geq 0$. (always remember that $n,l \geq 0$ and $m>0$)

In other worlds: \begin{equation} n+im+l=2^{p_i}\;\;,\forall\; i\geq 0\;(1) \end{equation}

If we plug in $i=0$ at the last equation we obtain a new relation: \begin{equation} n+l=2^{p_0} \;(2) \end{equation} Now if we substitute $(2)$ into $(1)$ we get: \begin{align} im &=2^{p_i}-2^{p_0}&\;\;,\forall\; i\geq 0\Rightarrow\\ im &= \text{even} &\;\;,\forall\; i\geq 0\Rightarrow\\ m&=2k \end{align},for some $k\in\! \mathbb{N}$.

The equation $(1)$, now, takes the form: \begin{equation} i\!\cdot\!2k=2^{p_i}-2^{p_0}\;\;,\forall\; i\geq 0\;(1.1) \end{equation} If we plug in $i=n+l$ at $(1.1)$ we obtain: \begin{align} 2^{p_0}\!\cdot\!2k&=2^{p_N}-2^{p_0}\Rightarrow\\ 2k&=2^{p_N-p_0}-1 \end{align} A contradiction. Therefore the initial assumption—that $L$ is a regular language—must be false. (lets note that $p_n\geq p_0$ since $\{p_i\}$ is a increasing sequence)

$\endgroup$
  • $\begingroup$ In the third paragraph, just after the pumping lemma conditions, should that be $w = a^{2^{p}}$? $\endgroup$ – Luke Mathieson Feb 2 '15 at 23:56
  • $\begingroup$ @LukeMathieson you are right i have it edited thanks $\endgroup$ – Karalis Charalampos Feb 3 '15 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.