# Using pumping lemma

I'm trying to prove that the language $\mathcal L = \{w \in \{0,1\}^* ∣ w \leq w′ \text{ where }w′ \text{ is any rotation of }w\}$ is not a regular language.

Note: The inequality is with respect to lexicographic order. And if $w=xy$, then $yx$ is a rotation of $w$.

I was thinking of using the string $s = 0^{P}1$ with $P$ being the pumping length, but I can't figure out how to pump this in a way to show a contradiction. Any help will be greatly appreciated.

HINT: If $p$ is the pumping length, start with $s=0^p10^p1$ and pump down.
• @Vimzy: The pumping lemma says that $s$ decomposes as $xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. The original $s$ has $k=1$; pumping down is setting $k=0$. – Brian M. Scott Feb 9 '16 at 21:53
• @Vimzy: $0^p10^p1$ is in $L$: no rotation has more than $p$ leading zeroes. – Brian M. Scott Feb 9 '16 at 22:03