2
$\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?

Improve this question
$\endgroup$
6
  • 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
    Commented May 20, 2015 at 13:29
  • 1
    $\begingroup$ Check our reference questions. $\endgroup$
    – Raphael
    Commented May 20, 2015 at 14:25
  • $\begingroup$ possible duplicate of How to prove that a language is not regular? $\endgroup$
    – D.W. ♦
    Commented May 20, 2015 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
    Commented May 20, 2015 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
    Commented May 20, 2015 at 21:32

1 Answer 1

Reset to default
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).

Improve this answer
$\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.