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