[Solved]: Language of the graph of an affine function

Problem Detail: 

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

Asked By : Gilles

Answered By : sdcvvc

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/641

3.2K people like this

 Download Related Notes/Documents