# Prove the language of numbers divisible by 3 is not regular using pumping lemma

I have a language $L$ that I think is not regular:

$L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$

I'm using pumping lemma in my proof. My main main idea is the following. I choose $w = 3$, according to the pumping lemma $w = xyz$ with $xy^iz$ where $i \in \mathbb{N}_0$. But for $i=0$ we have $\varepsilon$ which is not in the language ($\varepsilon$ is not divisible by 3). Therefore the language is not regular.

Is my idea right?

• The language is regular. Note that a decimal number is divisible by 3 if and only if the sum of the digits is divisible by 3. Cou can create an automaton with 3 states, where each state represents the current sum of digits modulo 3 while reading your decimal input. May 20 '15 at 13:29
• Check our reference questions.
– Raphael
May 20 '15 at 14:25
• possible duplicate of How to prove that a language is not regular?
– D.W.
May 20 '15 at 17:02
• IMHO there is no reason to downvote this question. If the OP understood the issue, he would not be asking,. So making errors is natural. At least he tried to make progress, and he is reporting it as expected. May 20 '15 at 21:20
• @Danny The automaton is slightly easier to write in the case of 3 because of the property you rightly state in your comment. However, the way to design the automaton is essentially the same independently of the chosen divider. You could replace 3 by any integer $n$ and the construction of the automaton would still work, with $n$ states, of course. It is only that defining each transition would require a bit (more) of very elementary arithmetics. May 20 '15 at 21:32

You cannot choose any string for the pumping lemma. You have to choose one that is at least as long as the pumping distance of the language (which exists when it is regular), but you do not know which it is, so you have to assume it is some value named $p$ (or some other name) and you assume you have a well chosen string in the language that is greater than $p$.
Another point is that I would say that $\epsilon$ is not the representation of a decimal number, rather than say it is not divisible by $3$.