Is it decidable if this zipping operation gives a context-free language?


Motivation

Consider the following languages, are they context-free?

  • $ \{x \# y: x \neq y\}$
  • $ \{x y: |x|=|y|, x \neq y\}$
  • $ \{x \# y: |x|=|y|, x \neq y\}$
  • $ \{x y: |x|=|y|,d(x,y)>1\}$

The first three are explained here, the last one is this question.

I’m wondering whether there is an algorithm to solve this kind of problem in general.

Question

Given two strings $ x,y$ , let $ \operatorname{zip}(x,y)$ denote the string $ (x_1,y_1)(x_2,y_2)\dots(x_n,y_n)$ . Note that letters in $ \operatorname{zip}(x,y)$ are pairs. If one string is shorter, we pad it with an extra blank symbol.

Is the following problem decidable?

Given a regular language $ L$ , is $ \{x y: \operatorname{zip}(x,y) \in L\}$ context-free?

If the answer is positive, we can solve the four problems from the motivation section by picking a suitable $ L$ .