Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ be integers, with $a > 0$. Consider the language of solutions of the Diophantine equation $y=ax+b$:

$$L = \{ \bar{x} \mathtt: \bar{y} \mid y = a\,x + b \}$$

Is $L$ regular? context-free?

(Contrast with Language of the values of an affine function)

(Follows on How can solutions of a Diophantine equation be expressed as a language?)

I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.

  • $\begingroup$ Wouldn't $\{ \bar{x} \mathtt: \bar{y}^{-1} \mid y = a\,x + b \}$ be much more interesting? Or do you think this should be a different question? $\endgroup$
    – jmad
    Mar 22 '12 at 2:40
  • $\begingroup$ @jmad Definitely a different question, since the answer is different. $\endgroup$ Mar 22 '12 at 9:20
  • $\begingroup$ Are you asking "Is $L$ regular/cf for all $a,b$?" or "For which $a,b$ is $L$ regular/cf?"? Also, note that the answer to the question changes if we encode number with a unary alphabet. $\endgroup$
    – Raphael
    Mar 22 '12 at 15:49
  • $\begingroup$ @Raphael Take your pick, since the answer doesn't depend on the values of $a$ and $b$. I did specify decimal; any base would do, whereas a unary notation does change the answer. $\endgroup$ Mar 22 '12 at 16:01
  • $\begingroup$ @Gilles: The answer might not depend on the interpretation, but a proof might. For instance, my (hidden) one solves the first, but not the second interpretation. $\endgroup$
    – Raphael
    Mar 22 '12 at 16:02


$53 \cdot 100000010000000000 + 4 = 5300000530000000004$.


Assume $a$ has $n$ digits and $b$ has $m$ digits.
If $\overline{x}=10^k \underbrace{00\dots01}_{n}0^l\underbrace{00\dots0}_{m}$ for some $k,l$ then $\overline{ax+b}=\overline{a}0^k \overline{a} 0^l \overline{b}$.
If $L$ was context-free, then $$L'=L \cap 10^{\ast}0^{n-1}10^{\ast}0^m \mathtt: (0+1+2+...+9)^{\ast} = \{10^{k+n-1}10^{l+m} \mathtt: \overline{a}0^k\overline{a}0^l\overline{b}:k,l \in \mathbb N\}$$ would be context-free as well. Given a PDA $M$ for $L'$ we could construct a PDA $N$ for $\{a^n b^m c^n d^m\}$ , a well-known non-context-free language. $N$ simulates $M$, but it is "feeding" different letters; it is a composition of $M$ with a transducer. Initially, $N$ behaves as if $M$ read $1$. Then, consecutive $a$'s are interpreted as $0$'s. Next, $N$ behaves as if $M$ read $0^{n-1}1$, and treats consecutive $b$'s as $0$'s, then as if it read $0^m \mathtt: \overline{a}$ etc.

  • $\begingroup$ That's clever. The hint alone wasn't enough; I'd seen that but hadn't realized you could subsequently do <spoiler> to get to a classical example. $\endgroup$ Mar 22 '12 at 19:05
  • $\begingroup$ Beautiful. I stand outclassed. $\endgroup$
    – Raphael
    Mar 22 '12 at 19:11

Regarding "Is $L$ regular?": You should reflexively check the Pumping condition; can a long solution $\bar{x}:\bar{y}$ be pumped?

No, it can not. Assume a pumping constant $p$. Because $y = ax + b$ has arbitrarily large solutions ($a>0$ !), we can choose one solution $(x',y')$ with $|\bar{x'}| > p$. Then, $xy$ (from the Pumping Lemma) has to be a prefix of $\bar{x'}$. Pumping $y$ now increases $x'$ but $y'$ remains unchanged; we leave $L$.

As for "Is $L$ context-free" (assuming above question was answered negatively) it is wortwhile to consider special cases of $L$, as the question implicitly asks wether $\{L_{a,b}\} \subseteq \mathrm{CFL}$. Can you find a combination of $a,b$ that allows an easy proof?

Indeed! $a=1$ and $b=0$ leads to $L = \{\bar{x}:\bar{x} \mid x \in \mathbb{N}\}$. We know that this language is not context-free by $\{ww \mid w \in \{a,b\}^*\}$ (the canonical example).

  • $\begingroup$ How does that work to pump harder, to show the language is not context-free? $\endgroup$ Mar 22 '12 at 9:25
  • $\begingroup$ Pumping in the context-free sense should destroy the solution, too, but I don't have a formal proof of that yet. $\endgroup$
    – Raphael
    Mar 22 '12 at 10:48
  • $\begingroup$ I'd gotten this far; doing the multiplication or the addition is where I get lost. $\endgroup$ Mar 22 '12 at 16:01

Hint 1: What happens when $a=1$ and $b=0$?

OK, we nailed it for a specific pair $a,b$. Now, does it will become any different for other $a,b$?

Hint 2: Go on with $b=0$ and arbitrary $a$

Hint 3: Try to think what happens if $a=0$ and $b$ is not. This can't happen in this question, but it should give you the idea how to cope with $a,b \ne 0$.

  • 1
    $\begingroup$ Hint 2.2 is where I'm stuck. What closure property can transform $\{\bar x:\bar x\}$ to handle the additions and multiplications? $\endgroup$ Mar 22 '12 at 9:24
  • $\begingroup$ I guess I meant looking at something like $L'=\{x:xy\}$ for any $y$. However now I'm not so sure anymore it is so easy to get via closure properties. $\endgroup$
    – Ran G.
    Mar 22 '12 at 16:25
  • $\begingroup$ @Gilles It should be just easier to pump. Thanks for your comment! I'll edit the answer. $\endgroup$
    – Ran G.
    Mar 22 '12 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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