# Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?

For two words $$w,v \in\{0,1\}^*$$ of equal length, let $$w+v \in\{0,1,2\}^*$$ denote the word in which the $$i$$-th word is the sum of $$i$$-th position of $$w$$ and $$v$$, as follows: if $$w=a_1 \ldots a_n$$ and $$v=b_1 \ldots b_n$$, then $$w+v=c_1 \ldots c_n$$, where $$c_i=a_i+b_i$$ for each $$i\in \{1, \ldots, n\}$$.

Assume $$L \subseteq \{0,1,2\}^*$$ is a regular language. Decide whether the language $$K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$$ is regular.

I would appreciate any hint as I don't know how to start. I know that the every word u+v can be easily converted to be over the alphabet $$\{0,1\}^*$$ such that $$h(a_i) = 0$$ if $$a_i=0$$ and $$h(a_i) = 1$$ if $$a_i=1$$ and if $$a_i = 2$$, then $$h(a_{i+1})=a_{i+1}+1$$. Then $$u+v$$ is just binary addition.

It might be easier to consider the complement of your language: $$\overline{K} = \{ u \in \{0,1\}^* : \exists v \in \{0,1\}^{|u|} \text{ s.t. } u+v \in \overline{L} \}.$$
You can now easily convert an NFA for $\overline{L}$ to one for $\overline{K}$ by replacing all edges labelled $1$ with edges labelled $0,1$ and all edges labelled $2$ with edges labelled $1$.