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