# Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

Is the language $L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\}$ regular?

My approach: let the $p$ be from the Pumping Lemma. Chose the smallest $n$ which has even number of digits in 10-base system, but bigger or equal to $p$, that is $n = 10^{2m - 1}$ for appropriate $m$.

According to the Lemma, $z = a^n = a^{10^{2m - 1}} = uvw$, and $|uv| \leq p$, with $v\neq \varepsilon$. So, we pump down $v$, and we got the $z'$ which should be in $L$ (by the Lemma). That is $uw$ should be in the language. If $|v|$ is smaller than $10^{2m-1} - 10^{2m-3}$, than we reach a contradiction. If $|v|$ is bigger, than we pump it up 10 times, to reach a contradiction again. I hope this is alright.

• Actually you can use the pumping lemma in a very elementary way that does not even need details. You know there is a length $p$, and that you need a string longer than $p$ in the language: can you do that? If you have such a string, it tells you that there is a substring, say $s$, that is not empty, and that can be repeated arbitrarily, without getting out of the language. Can there be such a string? if no, you have a contradiction. Commented May 4, 2015 at 12:21
• I did not check out the details of the arithmetics, but that is the idea for the reasonning. Commented May 4, 2015 at 13:31
• Hint: Myhill-Nerode. See also our reference questions. Commented May 4, 2015 at 13:36

A slightly simpler way is to say that if you consider a string $x\in L$ of size $p$, then there is a non-empty substring $v$ of $x$ that you can pump without getting out of the language, if it is regular. Then you can pump it in $x$ until it exceeds a size $10^{2m}$, which has to be greater than $p$, such that $10^{2m+1}-10^{2m} > |v|$. And you necessarily get the wrong number of digits.
In other words, you try to find in the sequence of possible sizes a gap that is too wide to be jumped by pumping a constant pumping size $|v|$.