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