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

Bounty: 200


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.


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

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!!!

Leave a Reply

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