1
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Danny May 20 '15 at 13:29
  • 1
    $\begingroup$ Check our reference questions. $\endgroup$ – Raphael May 20 '15 at 14:25
  • $\begingroup$ possible duplicate of How to prove that a language is not regular? $\endgroup$ – D.W. May 20 '15 at 17:02
  • $\begingroup$ 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. $\endgroup$ – babou May 20 '15 at 21:20
  • $\begingroup$ @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. $\endgroup$ – babou May 20 '15 at 21:32
4
$\begingroup$

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

All this being said, modular arithmetics works pretty well with divisibility constraints, divisibility by a constant, I mean. And Finite Automata are usually friendly to modular arithmetics because it is defined on finite sets of values (or classes of numbers).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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