# Irregularity of language of words whose length is of power of 2 [duplicate]

How to show that the language containing the words whose length is a power of $$2$$, $$L=\{w\mid|w|=2^i\}$$, isn't regular using the pumping lemma?

The pumping lemma says that

Let be M a regular language. Then it exists a number $$p>0$$ such that for each word $$w\in L$$, such that $$|w|\ge p$$, it exists $$x,y,z$$ such that :

1. $$w=xyz$$
2. $$|y|>0$$
3. $$|xy|
4. For each $$i\ge 0$$ we have $$xy^iz\in L$$.

(I don't perfectly understand this lemma...). I have great difficulties to understand the examples which I can provide you in French here.

My question is different from How to prove that a language is not regular? as far as all answers are based on $$L=\{w\mid|w|=a^pb^q\}$$ scheme, mine only have one element and is playing on the size rather than the scheme.

### My attempt

We take $$w=a^{2^n}$$. Therefore we have $$w\in L$$ and $$|w|\ge p$$. We need a partition $$w=xyz$$ (to fill in condition 1.) such that $$|xy| (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) and we reach a contradiction.

I have some difficulties understanding the conclusion.

• Our reference question may be of help here. Commented Apr 14, 2017 at 15:05
• @Raphael Thank you for this link. I think it allowed me to achieve the exercise but I'm still not able to understand its conclusion... Commented Apr 15, 2017 at 13:31
• It makes no difference that this question has an alphabet of size one, compared to the reference question which tends to use size two. The same principles apply. Commented Jun 19, 2017 at 11:05

The strategy for proving a language non-regular is a proof by contradiction:

We assume that $L$ is regular. This then means that there exists a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3. But now it is enough to find some $w$ where $|w| \geq p$ such that no partition can satisfy all three conditions simultaneously.

In the concrete case, you have not told us what alphabet $\Sigma$ we are considering. I assume that $\Sigma = \{ a,b\}$, but this is not important.

So we assume that $L$ is regular, and therefore there must exist a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3.

But now consider $w = a^{2^p}$. Clearly, $w \in L$. Moreover, we have that $|w| \geq p$, so there should be some partition of $w = xyz$ that satisfies conditions 1, 2 and 3.

If the partition must satisfy condition $3$ then the first two parts of the partition, that is, $xy$, must have total length less than $p$. Therefore, $|y| \leq p$. If the partition must also satisfy condition $2$, then $y$ cannot be the empty string, so $y = a^k$ for some $k$ where $0 < k < p$.

But can such a partition then also satisfy condition $1$? No. It is enough to find an $i \geq 0$ such that $xy^iz \notin L$ to see this. Take $xy^2z$. This string has length $2^p + k$, and since $k < p$, we know that $2^p + k$ cannot be a power of $2$. So $xy^2z \notin L$.

In other words: The appropriate strategy is to try to satisfy the conditions one by one. Usually, we first try to satisfy condition $3$. This will tell us where $y$ can appear (among the first $p$ symbols) and how long it can be. Given that, we then try to also satisfy condition $2$, and this usually just provides with the useful information that the string $y$ that can be repeated, is non-empty. Finally, we show that we can "pump our way out" of the language with this partition, thereby violating condition $1$.

Consider any $DFA$ which represents a regular language $L$. Now, the $DFA$ may have loops in it.

Pumping Lemma is about identifying strings $w$ such that $x$ and $z$ are the non-loop parts and $y$ is the string parsed in the loop part. Now, if such a $w$ is accepted by the $DFA$, $xy^iz$ is also a string of the language.

Now, to prove that the given language is not regular, try to find such a $y$ and pump it. For arbitrary values of $xy^iz$, we can see that length of $w$ is not a power of $2$ as follows using proof by contradiction:

Assume that the given language is regular. Hence, by pumping lemma we have a $p > 0$

such that for strings $|w| >=p$ the lemma holds.

Now, consider the closest power of $2$ greater than $p$.
It can be written as $2^{\lfloor{lgp}\rfloor+1}$.
Let's call the exponent $a$. Hence $$a = \lfloor{lgp}\rfloor+1 \tag{1}$$ Clearly $2^a > p$ hence, pumping lemma holds true for strings $w$ of length $=2^a$.

Consider any such $w$. Let's write it as $xyz$ such that $|xy| < p$.
Clearly $|y| < p$.
Hence $$|y| < 2^a . \tag{2} \label{eq:2}$$ Now, consider the new string $xy^2z$.

$|xy^2z| = |xyz|+|y|$
=> $|xy^2z| = 2^a + |y|$
=>$|xy^2z| < 2^a + 2^a$ from \eqref{eq:2} above
=> $|xy^2z| < 2*2^a = 2^{a+1}$

Hence, the new string constructed from pumping lemma has a length between two consecutive powers of $2$, so it cannot be a string of the original language.

As this holds for all values of $x, y, z$ satisfying the constraints of the lemma for the given string, we can say that the original language is not regular.

Hence proved that the language is not regular.

Your language is a unary language (a subset of $\sigma^*$ for some letter $\sigma$). You can prove in various ways the following theorem:

The language $\{ \sigma^n : n \in A \}$ is regular if and only if the set $A$ is eventually periodic, that is, if there exist $n_0,m \geq 1$ such that $n \in A \leftrightarrow n+m \in A$ whenever $n \geq n_0$.

In particular, if the language is regular and the asymptotic density of $A$ is zero, then $A$ is finite. In your case the asymptotic density of $A$ is zero yet $A$ is infinite, and so the language is not regular.