Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 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 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
show 2 more comments

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
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 Mar 22 '12 at 19:05
    
Beautiful. I stand outclassed. –  Raphael Mar 22 '12 at 19:11
add comment

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

share|improve this answer
1  
Hint 2.2 is where I'm stuck. What closure property can transform $\{\bar x:\bar x\}$ to handle the additions and multiplications? –  Gilles 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
add comment

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

share|improve this answer
    
How does that work to pump harder, to show the language is not context-free? –  Gilles 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 Mar 22 '12 at 16:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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