Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\mid w_i\mid=n$ for all $i$, then set $w'\approx w$ if also $\mid w'_i\mid=n$ for all $i$ and there are permutations $\pi_1,\pi_2$ such that $w_i[j]=w'_{\pi_1(i)}[\pi_2(j)]$. $L$ is closed under $\sim$ and $\approx$.For example, if $100\#0000\#$ is in $L$, so is $0000\#100\#$. If $100\#110\#$ is in $L$, so are $110\#100\#$, $010\#011\#$, $011\#010\#$, etc. Additionally, set $w'\bowtie w$ if $w'\sim w$ and $\mid w_i\mid_1=\mid w'_{\pi_1(i)}\mid_1$ for all $i$ ($\mid \cdot\mid_1$ means ``number of 1's). $L$ is not closed under $\bowtie$. My question is: Are there context-free languages $L$ with these properties such that $L$ can not be written as a substitution $s(L_1)$ where $s(a)=L_a\#$ for some $L_1$ and $L_a$? Is it true that such an $L$ is context-free if and only if it is a substitution? I think this in fact equivalent to the conjecture that if $L$ is closed under $\sim$ and $\approx$ and context-free, then it is in fact closed under $\bowtie$. (The intuition being: how else could the permutation invariance be enforced context-freely unless a side effect of $\bowtie$-closure?).I have been trying to think about this in terms of matching relations ([1]). The idea is that a language is context-free if and only if for every string there is a matching (non-crossing pairing relation) and a first-order sentence that they together satisfy (so this sentence basically says that the arcs of the matching correspond to productions). If $L$ can be written as a substitution, every string will have matching where $\#$'s are paired and the symbols of every $w_i$ are paired up with symbols in the same $w_i$. I'm trying to show that if there are arcs that cross over a $\#$, (which means there are productions that generate symbols in distinct subwords), then there is a contradiction with the invariance properties.[1] Lautemann, Clemens, Thomas Schwentick, and Denis Thrien. Logics for context-free languages. Computer science logic. Springer Berlin Heidelberg, 1995.
Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution
formal languages;context free;formal grammars