Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Many thanks in advance.

share|improve this question
1  
I've tried to TeXify your post, please check if it is alright. –  dtldarek Jan 26 '13 at 14:05
1  
Are you talking about pumping lemma for regular or context free languages? –  Karolis Juodelė Jan 26 '13 at 14:12
    
Regular languages. Thanks. –  Epsilon Jan 26 '13 at 14:12
    
@MHZ, why don't you "accept" my answer? if it helped –  user58512 Jan 27 '13 at 11:12
1  
accepted! thanks for all the help! ;) –  Epsilon Jan 27 '13 at 14:24
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
@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
1  
@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
1  
@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
1  
@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
show 6 more comments

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. :-)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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