# Language of the graph of an affine function

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.

• 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? – jmad Mar 22 '12 at 2:40
• @jmad Definitely a different question, since the answer is different. – Gilles 'SO- stop being evil' Mar 22 '12 at 9:20
• 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. – Raphael Mar 22 '12 at 15:49
• @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. – Gilles 'SO- stop being evil' Mar 22 '12 at 16:01
• @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. – Raphael Mar 22 '12 at 16:02

Hint:

$53 \cdot 100000010000000000 + 4 = 5300000530000000004$.

Sketch:

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.

• 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. – Gilles 'SO- stop being evil' Mar 22 '12 at 19:05
• Beautiful. I stand outclassed. – 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).

• How does that work to pump harder, to show the language is not context-free? – Gilles 'SO- stop being evil' Mar 22 '12 at 9:25
• Pumping in the context-free sense should destroy the solution, too, but I don't have a formal proof of that yet. – Raphael Mar 22 '12 at 10:48
• I'd gotten this far; doing the multiplication or the addition is where I get lost. – Gilles 'SO- stop being evil' 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$.

• Hint 2.2 is where I'm stuck. What closure property can transform $\{\bar x:\bar x\}$ to handle the additions and multiplications? – Gilles 'SO- stop being evil' Mar 22 '12 at 9:24
• 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. – Ran G. Mar 22 '12 at 16:25
• @Gilles It should be just easier to pump. Thanks for your comment! I'll edit the answer. – Ran G. Mar 22 '12 at 16:57