3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Commented May 4, 2015 at 12:21
  • $\begingroup$ I did not check out the details of the arithmetics, but that is the idea for the reasonning. $\endgroup$
    – babou
    Commented May 4, 2015 at 13:31
  • 2
    $\begingroup$ Hint: Myhill-Nerode. See also our reference questions. $\endgroup$
    – Raphael
    Commented May 4, 2015 at 13:36

1 Answer 1

1
$\begingroup$

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|$.

This very simple reasonning also works with the context-free pumping lemma.

Wide gaps, that cannot be pumped exist as soon as empty gaps can increase in size beyond any bound. This depends on the definition of the language.

But using the pumping lemma is often a bit more sophisticated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.