4
$\begingroup$

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.

$\endgroup$
7
  • $\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
    Commented Mar 22, 2012 at 2:40
  • $\begingroup$ @jmad Definitely a different question, since the answer is different. $\endgroup$ Commented Mar 22, 2012 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
    Commented Mar 22, 2012 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$ Commented Mar 22, 2012 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
    Commented Mar 22, 2012 at 16:02

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Mar 22, 2012 at 19:05
  • $\begingroup$ Beautiful. I stand outclassed. $\endgroup$
    – Raphael
    Commented Mar 22, 2012 at 19:11
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How does that work to pump harder, to show the language is not context-free? $\endgroup$ Commented Mar 22, 2012 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
    Commented Mar 22, 2012 at 10:48
  • $\begingroup$ I'd gotten this far; doing the multiplication or the addition is where I get lost. $\endgroup$ Commented Mar 22, 2012 at 16:01
1
$\begingroup$

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

$\endgroup$
3
  • 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$ Commented Mar 22, 2012 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.
    Commented Mar 22, 2012 at 16:25
  • $\begingroup$ @Gilles It should be just easier to pump. Thanks for your comment! I'll edit the answer. $\endgroup$
    – Ran G.
    Commented Mar 22, 2012 at 16:57

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.