Is $L:=\{a^k \mid k \text{ is prime}\}$ regular? For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make sense to me since a while program always returns an element of the integers. How can I use code in my proof?
You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.