How to show that the language containing the words which length are of power of $2$, $L=\{w\mid\lvert w\rvert=2^i\}$ isn't regular using pumping lemma ?
I have some difficulties to understand the examples which I can provide you in French here.
My attempt
We take $w=a^{2^n}$. Therfore we have $w\in L$ and $|w|\ge p$. We need a partition $w=xyz$ (to fill in condition 1.) such that $|xy|<p$ (condition 3) and $|y|>0$ (condition 2).
- Let's assume $L$ is regular.
- I thought about taking $|w|>n$
- $x = aaaa....$ , $y = aaaa...$, $|x|=s$, $|y|=k$. We need to consider ALL the options, that is all the possible $s,k$ such that $s≥0$,$k≥1$ and $s+k≤n$.
Let's take $i=0$, then $xy^iz=xz=a^{n-k}a^n\not\in L$ whatever may $s,k$ be and since $k\ge 1$, $L$ isn't regular at all (but why) nd we reach a contradiction.
I have some difficulties to understand the conclusion I made up myself from examples. Therefore I'm not even sure I'm proving anything.
Here is how to use the pumping lemma:
Assume by contradiction that $L \in REG$.
Let $p \gt 0$ be the pumping constant of $L$.
First note that $2 \ ^ n \gt n $ for all $n \in \Bbb N $.
Let $w = a \ ^ {2 ^ p}$ so $|w| = 2 \ ^ p \gt p$ so by the pumping lemma we have $x,y,z \in \Sigma \ ^ *$ s.t the following holds:
$w = xyz$
$|xy| \le p $
$|y| \gt 0$
For all $i \in \Bbb N \cup \{ 0\}$ the word $x y \ ^ iz \in L$.
Denote by $j$ the length of $y$ , that is $y = a \ ^ {j}$ , $|xy| \le p$ so $j \le p$.
We have $xy\ ^ 2 z = a \ ^{2j} a \ ^ {2 \ ^ p -j} = a \ ^ {j + 2 \ ^ p}$.
Now we have that $2 \ ^ p \lt 2 \ ^p + j \lt 2 \ ^p +2 \ ^p= 2 \ ^{p+1} $ because $ j \lt 2 \ ^ p $.
So $|x y \ ^ 2 z| = j + 2 \ ^p$ is not a power of $2$ this is a contradiction because we need to have $xy\ ^ 2 z \in L$ .
Thus $L \notin REG$.