Quoting chandok's answer on MO 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.
