The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime.
I'm assuming the best way to move forward is to use the pumping lemma. I'm having difficulty developing a contradiction in this case because typically the membership criteria of the language involves some characteristic of the length of the members (e.g. the members are of length $n$, where $n$ is a perfect square), not their numerical value. Can someone help me apply the pumping lemma in this case?
Pumping lemma is the key. If the language were regular, thered be strings $u,v,w$ such that $uv^*w\subseteq L$ and $|v|>0$ and wlog $|u|>0$, i.e. $u\in 1\{0,1\}^*$ If $U,V,W$ are the numbers represented by $u,v,w$ (where $v,w$ may have leading zeroes), then the number represented by $uv^kw$ is $U\cdot 2^{|w|+k|v|} + 2^{|w|}\cdot \frac{2^{k|v|}-1}{2^{|v|}-1}\cdot V+W$, where $U\ge 1$. Show that these cannot all be prime.