# Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular

I'm trying to prove that the following language is not regular:

$$\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$$

I'm trying to prove this with the pumping lemma, but I'm kind of confused because $$w$$ is a language, not an expression like $$a^n b^n$$, and I don't know how can I partition that into three parts.

• $w$ is a word, your language simply consists of all binary strings that can be written as some number of repetitions of the same block Apr 13, 2021 at 9:49

Suppose towards a contradiction that your language $$L$$ was regular and let $$p$$ be its pumping length.

Consider the word $$w = 0^p 10^p1 \in L$$. By the pumping lemma, $$w$$ can be written as $$w=xyz$$ with $$x=0^{h}$$, $$y=0^k$$, and $$z=0^{p-h-k}10^p 1$$ (here $$h+k \le p$$ and $$k \ge 1$$) such that, for every non-negative integer $$i$$, $$xy^iz \in L$$.

Substituting and simplifying, the above means that, for every $$i \ge 0$$, we have $$0^{p-k} 0^{ki} 1 0^p 1 \in L$$. In particular, the above must hold for $$i=0$$, implying that $$0^{p-k}1 0^p 1 \in L$$. Since $$0^{p-k}1 0^p 1 \not\in L$$ (recall that $$k \ge 1$$), this is provides the sought contradiction and concludes the proof.

First to clear up: $$w$$ is not a language, it is an arbitrary string composed of the symbols $$0$$, $$1$$. The "plain English" definition of this language would be "all binary strings that can be expressed as two or more repetitions of any binary string (including the empty string)".

Examples of strings that are members of this language would be $$010010$$ ($$w=010$$), $$1111$$ ($$w=1$$ or $$w=11$$) and the empty string $$\epsilon$$ ($$w=\epsilon$$).

To prove this language non-regular by pumping lemma, assume there exists a pumping length $$p$$ for the language. Then let's construct a string belonging in the language with a length of at least $$p$$ that we can use to demonstrate the impossibility of a legal partition: I suggest $$0^p 1^p 0^p 1^p$$ which is a member of the language as $$w = 0^p 1^p$$.

Now it is fairly easy to see any $$xyz$$ partition using the rules of the pumping lemma is impossible. As $$|xy| \leq p$$ it must hold that $$y$$ = $$0^n$$ for some $$n \leq p$$. Therefore $$xy^2z = 0^{p+n}1^p0^p1^p$$. From $$|y| \geq 1$$ it follows that $$n \geq 1$$, therefore $$xy^2z$$ is not a member of the specified language, and there are no legal $$xyz$$ partitions.

This demonstrates the language doesn't have a finite pumping property, therefore it is not regular.