# #StackBounty: #context-free 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}$$
• $${x x}$$

The first three are explained here, the fourth one is this question, the last one is well-known.

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. For example, $$operatorname{zip}(aab,cd)=(a,c)(a,d)(b,blank)$$.

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 five problems from the motivation section by picking a suitable $$L$$:

• $${x x}$$ can be written using $$L=((a_1,a_1)+dots+(a_n,a_n))^{ast}$$ where $$a_i$$ are all letters of the alphabet except blanks.
• $${x y: |x|=|y|, x neq y}$$ can be written using $$L$$ which checks that in the pairs $$(a,b)$$ there is at least one mismatch $$a neq b$$ and there are no blanks.
• $${x y: |x|=|y|,d(x,y)>1}$$ is similar, the language $$L$$ checks if there are at least two mismatches and no blanks.
• $${x # y: |x|=|y|, x neq y}$$ is checking for at least one mismatch, and then expects a single symbol $$(#, blank)$$.
• $${x # y: x neq y}$$ is checking that the left component of the last character is $$#$$, that there is at least one mismatch, and unlike the previous examples blanks are allowed when checking for a mismatch.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.