Consider the following language over $\Sigma = \{0,1,...,9\}$: $$L=\{ww'b: w,w' \in \Sigma^*, |w|=|w'|, b \in \Sigma, \text{ for every i}: w_i = w'_i + b (mod 10)\}$$
To clarify, the equality of $w_i$ and $w'_i$ needs to hold up to a constant b (the modulo keeps it in the alphabet). Now, clearly this is not a CFL (pumping lemma, etc.). My question is, how and if the complement of L is a CFL. I want to explicitly find a grammar that produces it if so. So far i tried finding some trivial cases that belong to the complement (even length words, or words which don't hold the condition of the modulo operation, etc.), but i have no general way of deriving this grammar (if it exists at all). Is there some general way of obtaining it?
This is a somewhat more complicated version of a classic problem: show that the complement of this language is context-free:
$$L = \{ ww':w,w'\in \Sigma^*, w = w'\}$$
The key part of the answer is to divide the string $ww'$ in a different way:
$$ww' = xw_ix' yw'_iy' \text{ where }|x|=|x'|\text{ and }|y|=|y'|$$
This decomposition works because $|xy'|=|x'y|$. And each of the parts $xw_ix'$ and $yw'_iy'$ is pretty clearly context free ($W_i\to w_i \mid SW_iS; S\to s_i \text{ for each }s_i\in\Sigma$).
Although it can't help prove that $w=w'$ (which requires that every $w_i=w'_i$), it can produce the set of strings where some $w_i\ne w'_i$. That requires $O(|\Sigma|^2)$ productions to enumerate all the pairs of unequal symbols ($L\to W_iW_j\text{ for all }0\lt i,j\le|\Sigma|, i\ne j$)
In your problem, you have the additional wrinkle of $b$; however, that just increases the number of cases to enumerate to $O(|\Sigma|^3)$.