Using pumping lemma

207 Views Asked by At

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.

1

There are 1 best solutions below

7
On BEST ANSWER

HINT: If $p$ is the pumping length, start with $s=0^p10^p1$ and pump down.