In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.
I have not been able to solve this one:
The set of strings of 0s and 1s, beginning with a 1, and interpreted as an integer, that integer is prime.
Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....
Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).