Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?


One case this is possible is when $\pi(w)$ is the string reverse permutation (CFG is describing palindromes).


Are there other choices for $\pi(w)$ with polynomial size CFGs?


**Explanation**: $n$ and $\pi$ **are fixed per language**. $\pi$ depends on $n$ (the indices of the letters of $\pi(w)$ are a permutation of {1..n} corresponding to indices {1..n} in $w$). How is $\pi$ fixed - two sub-cases:


1. The answerer can choose $\pi$ (or a class of $\pi$s), having in mind the string reverse case is solved.
2. $\pi$ can vary over all permutations. Again, $\pi$ is fixed per language.


Any references to what languages can be described by polynomial size CFGs (I found only several papers by Asveld, P.R.J. dealing with permutations and circular shifts over large alphabets).


Polynomial size is defined as the size of the Chomsky Normal Form. I included CNF on purpose. In case several answers are given, the size of the CNF will show the ``smaller'' solution.



Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?
Quoting [chandok's answer on MO](https://math.stackexchange.com/questions/19691/can-a-polynomial-size-cfg-describe-the-finite-language-w-piw-piw-is/19727#19727) in community wiki mode.


I think a more precise question would be :


Given a permutation $\pi$ of {1...n}, what is the size of a grammar describing $L\_\pi = \{w\pi (w), |w|=n\}$. 


In fact, there is not a lot of ways to build such a grammar : if you use a symbol that can develop into different words, i.e. that can put either a 0 or a 1 in a certain position of the final word, then that symbol has to take care simultaneously of the corresponding position in the other half of the word.
This means that the only way to have a nontrivial rule is when the permutation $\pi$ has a property 
$$\pi(\{n-k+1...n\}) = \{1...k\}$$
If this is the case we can split the permutation into two components $\sigma$ and $\tau$ such that :
$$\forall i \in \{1..k\}, \pi(n-k+i) = \sigma(i) \quad \text{and} \quad \forall j \in \{1...n-k\}, \pi(j) = k+\tau(j)$$
Then, we can use the fact that $L\_\pi = \bigcup\_{|w|=n-k} w L\_\sigma \tau(w)$ 


For example, with $rev\_n$, the reverse permutation on {1...n}, we do have $rev\_n(\{2...n\}) = \{1...n-1\}$, thus we get the equality $L\_{rev\_n} = 0L\_{rev\_{n-1}}0 + 1L\_{rev\_{n-1}}1$, which translates into a linear sized grammar for $L\_{rev\_n}$.


In the general case, you get exponentially bigger grammar rules as you have to decide on a greater number of letters of $w$ at the same time. The worst case (which happens pretty often) is when you can't write any non-trivial rule, and then have to enumerate all the words of $L\_\pi$, for example if $\pi = id\_n$. The better cases are the permutation that are close to the reverse permutation for example if n is even and $\pi(i) = (n-i+1+(-1)^i))$


Edit : Let me give a more precise estimation of the size of such a grammar.
Define S to be the subset of {0...n} consisting of those integers k such that $\pi(\{n-k+1...n\}) = \{1...k\}$. S = {k1=0, k2, ..., kp = n} (0 and n give trivial decompositions and are always in this set).


Then the shortest grammar uses (p-1) symbols S\_0 ... S\_{p-1}, and each rule is of the described format, where to expand Si we have to choose $\delta\_i = k\_{i+1}-k\_i$ letters before expanding the next symbol $S\_{i+1}$. Thus the "size" of the grammar is about
$\Sigma\_{i=0}^{p-1} \delta\_i 2^{\delta\_i}$.


If you choose a family of partitions that keep the gaps $\delta\_i$ small (for example bounded), you get a linear-sized grammar (there are a linear number of symbols and each rule is about the same size). If you allow them to grow slowly (for example around log(n)), you can still get a polynomial-sized grammar. Since it's not clear what kind of families of permutations you're thinking about, I can't get more precise than that.


