Prove the following language is irregular.
$$ \{w^n \mid w \in \{0,1\}^*,\ n ≥ 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.
On
Hint. Suppose that your language (call it $L$) is regular. Since regular languages are closed under intersection, the language $L \cap 0^+10^+1$ would also be regular. I let you verify that this intersection is equal to $\{0^n10^n1 \mid n > 0 \}$. Now you should be able to prove that this latter language is not regular.
Proof by contradiction: let's assume the language was regular and had a pumping length of $p$. Now construct the string $s = (0^{p}1)^2$, which is clearly in the language since $w = 0^{p}1 \in (0|1)^*$.
According to the pumping lemma, we must be able to perform some decomposition $s = xyz$ such that $|y| \geq 1$, $|xy| \leq p$, and $xy^az$ in in the language for all $a \geq 0$.
Part of the tricky part of dealing with the pumping lemma is its breadth: we've cast such a wide net that it's difficult to know how to proceed. So, it often helps in these problems to narrow our view to a smaller case which gives a clearer path forward.
So let's consider the case where $a = 0$, meaning we have to find some non-empty substring $y$ which can be removed so that $xz$ is still in the language, noting that $|xy| \leq p$ implies $|y| \leq p$. Remember that we can specify our $a$ like this because the pumping lemma has to hold for all $a \geq 0$, so if we fail when $a = 0$ then we fail the pumping lemma as a whole.
It should be clear that $y$, as any substring of $s$, must contain either $0$, $1$, or $2$ ones, so let's look through each possibility to see where this gets us.
Case $1$: $y$ has no ones
Let's say $|y| = l, 1 \leq l \leq p$ and $y$ contains no ones. This gives us two options: either $x = 0^{p-l-m}, y = 0^l, z=0^m10^p1$ or $x = 0^p10^m, y =0^l, z=0^{p-l-m}1$ for some $0 \leq m < p$. This gives us either $xz = 0^{p-l}10^p1$ or $xz = 0^p10^{p-l}1$, both of which are of the form $0^a10^b1$ where $a \neq b$.
For a string to be in the language it has to be writable as $w^n$ for some $w \in (0|1)^*, n \geq 2$. Clearly $n > 2$ is impossible here because there are $2$ ones in $xz$, so if $w$ contains no ones then $w^n$ contains no ones and if $w$ contains at least $1$ one then $w^n$ must contain at least $n$, which is more than $2$.
So, for $xz$ to be in the language there must be some $w$ such that $w^2 = xz$. Clearly because $xz$ ends with a one, $w$ must also end with a one, so $w = 0^c1$ for some $c \geq 0$ and $w^2 = 0^c10^c1$. However, as mentioned before, xz is always of the form $0^a10^b1$ where $a \neq b$, so there can be no $w$ such that $w^2 = xz$. Thus we can conclude that $xz$ is not in the language, which leads us to a contradiction.
Case $2$: $y$ has $1$ one
I know the first case was pretty long, but thankfully the next two cases are pretty easy to deal with. If $y$ contains $1$ one and $s = xyz$ contains $2$, then clearly $xz$ contains exactly $1$. Now using the same argumentation we've used before, there can be no $w$ such that $w^n = xz$ for $n \geq 2$ because $w$ must contain a one, but if $w$ contains a one then there must be at least $n$ ones, which is at least $2$. So we can conclude that $xz$ cannot be in the language.
Case $3$: $y$ has $2$ ones
For $y$ to be a substring of $s$ and have $2$ ones, we must have $y = 0^m10^p1$ for some $0 \leq m \leq p$. However, this must always be at least $p + 2$ characters long, which contradicts $|y| \leq p$. So, $y$ can never have $2$ ones.
Now, we have that $y$ must have $0$, $1$, or $2$ ones, but each of these leads to a contradiction, therefore we can conclude that we cannot choose a $y$ which satisfies the pumping lemma. Therefore, the language is irregular.
Hope this helps! Sorry if it's a bit long-winded.