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.

  • $\begingroup$ When you say pump down, do you mean take the divided string's pumpable portion and go from something like say 5, down to 4, 3, etc? $\endgroup$ – Vimzy Feb 9 '16 at 21:51
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Feb 9 '16 at 21:53
  • $\begingroup$ But s=0p10p1 wouldn't even be a part of the language L? On certain rotations, 0p10p1 is greater than the rotation? $\endgroup$ – Vimzy Feb 9 '16 at 22:00
  • $\begingroup$ @Vimzy: $0^p10^p1$ is in $L$: no rotation has more than $p$ leading zeroes. $\endgroup$ – Brian M. Scott Feb 9 '16 at 22:03
  • $\begingroup$ I think I may just be misunderstanding the lexicographic condition here, but isn't 0101 when rotated to 0011 come out to 0101>0011? I think I may have a misunderstanding here? $\endgroup$ – Vimzy Feb 9 '16 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.