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

Question

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|<p$
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|<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) and we reach a contradiction.

I have some difficulties understanding the conclusion.

Answer 1

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

Answer 2

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 \begin{equation} a = \lfloor{lgp}\rfloor+1 \tag{1} \end{equation} 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 \begin{equation} |y| < 2^a . \tag{2} \label{eq:2} \end{equation} 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.

Answer 3

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.