# Pumping Lemma proofs

I am having a hard time writing a Pumping Lemma contradictory proof for the below statements.

1) $L_1 = \{ ww \mid w \in E^* \}$ <--- I don't understand how to read this. This is what I tried: For any string (of any length) that can be cut down the middle there exists and element of any length? so I would have to pick a string of length X that when I split the string in half, it still can be any length? this is really confusing to try to prove, i'd appreciate any suggestions with this one.

2) $L_2 = \{ a^{2^n} \mid n \geq 0 \}$ <---- same with this, I don't understand what kind of string I would have to pick to disprove this.

Note: That is a Pumping Lemma is for Regular Languages.

I'd appreciate any hints or comments that may help me disprove these.

• I've tried to TeXify your post, please check if it is alright. – dtldarek Jan 26 '13 at 14:05
• Are you talking about pumping lemma for regular or context free languages? – Karolis Juodelė Jan 26 '13 at 14:12
• Regular languages. Thanks. – AnchovyLegend Jan 26 '13 at 14:12
• accepted! thanks for all the help! ;) – AnchovyLegend Jan 27 '13 at 14:24

For (1) the language is repeated strings from some alphabet. If $E$ was $\{0,1\}$ then $E^*$ is all binary strings and the language is $\{,00,11,0000,0101,1010,1111,000000,001001,\ldots\}$. It suffices to prove this language is not regular for $E=\{0,1\}$ since intersections of regular languages are regular. Now suppose the machine that recognizes it has $n$ states and consider the double of a binary string of length $n$: you must be able to pump one half of it and not the other.. so pick the string of length $n$ that looks like 1000[n zeros]001, but doing that breaks the property that it it is a double.

For (2) the language is $\{a,aa,aaaa,aaaaaaaa,aaaaaaaaaaaaaaaa,\ldots\}$.

Suppose it was recognized by a machine of $n$ states, consider the smallest $i$ such that $n \le 2^i$. In matching the string $a^{2^i}$ some substring must pump. Suppose that substring had length $k \le 2^i$. Then the machine must also match $a^{2^{i} + k}$ and $a^{2^{i} + k + k}$ one of which is not a power of two.

• @MHZ, take 1000110001 and pump the left half, e.g. 1000000000110001 – user58512 Jan 26 '13 at 14:24
• @MHZ, the $ww$ means that the two halves are the same. – Karolis Juodelė Jan 26 '13 at 14:28
• @user58512, sorry, I now see that my comment was wrong. I confused the condition that $|xy| < p$ with one that $|y| <p$. I'll erase it... – Karolis Juodelė Jan 26 '13 at 14:34
• @MHZ, We assume the machine has some finite number $n$ states. We reason that strings longer than $n$ must contain a substring that can pump (be repeated indefinitely). I decided to pick a string of length $2n$ so that we could pump the first half of it! That means if we use a string like 10[00]0011000001 which is in the language (using brackets to denote the part which can be pumped) then so is 10[00][00]0011000001.. but that gives a contradiction since it's not a doubled string. The contradiction disproves that the language is regular. – user58512 Jan 26 '13 at 14:50
• @MHZ, pumping lemma says that, if you take a long enough word in a regular language, there will be some short enough substring in it, that you can repeat any number of times and still get only words in the language. He picked some large word of length $2^n$ and a substring in it of length $k$. Because $2^n+ik$ can't always be a power of $2$, the above condition doesn't hold. – Karolis Juodelė Jan 26 '13 at 15:46

MHZ, maybe the url, http://www.comp.nus.edu.sg/~sanjay/cs4232/t4ans.pdf, will help you with some idea. See question 1, through (a) to (d). After reading it, maybe you konw how to prove it. :-)