Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language {$w \pi_1(w) \pi_2(w)$} over alphabet {0,1}?

Polynomial size in $|w|=n$

  • $\begingroup$ You mean a polysize CFG for $L_n = \{w\pi_1(w)\pi_2(w) : w \in \{0,1\}^n\}$? $\endgroup$ Commented Feb 16, 2011 at 17:34
  • $\begingroup$ Also asked on cstheory. $\endgroup$ Commented Feb 16, 2011 at 17:40
  • $\begingroup$ You really need a sequence of permutations $\pi_1^n,\pi_2^n$, one of each possible size. $\endgroup$ Commented Feb 16, 2011 at 17:42
  • $\begingroup$ The only way to describe such a language with a CFG is by enumerating its words, there is really nothing good you can do. $\endgroup$
    – mercio
    Commented Feb 16, 2011 at 21:23
  • $\begingroup$ @Chandok: That requires proof. If $w$ appeared only twice, then there is a choice of $\pi$ that results in poly-size grammars, namely the reversing permutation, which requires only a linear size grammar. $\endgroup$ Commented Feb 17, 2011 at 3:20

1 Answer 1


Without loss of generality, we can assume that a grammar for $L_n$ (such a language with specific $\pi_1,\pi_2 \in S_n$) is in Chomsky Normal Form. The language $L_n$ consists of the words $w(x) = x\pi_1(x)\pi_2(x)$ for all $x \in \{0,1\}^n$.

Using the Subword Lemma (see my previous answers), for each $w(x)$ we can find a substring $s(x)$ of length $$\frac{n}{2} \leq |s(x)| < n$$ generated by some symbol $A(x)$ and occurring at position $p(x)$.

Suppose that $p(x) = p(y)$ and $A(x) = A(y)$. Since $|s(x)|<n$, the subword $s(x)$ cannot intersect both the $x$ part and the $\pi_2(x)$ part of $w(x)$; we can assume it is disjoint from the $x$ part. Thus $w(x)$ is of the form $x \alpha s(x) \beta$. This implies that $A(x)$ generates exactly one string, namely $s(x)$. Therefore $s(x) = s(y)$.

Now $s(y)$ intersects either $\pi_1(y)$ or $\pi_2(y)$ in at least $n/4$ places, and thus determines at least $n/4$ bits of $y$. Therefore at most $2^{3n/4}$ strings $y \in \{0,1\}^n$ can have $p(x) = p(y)$ and $A(x) = A(y)$. Since there are at most $3n$ possibilities for $p(y)$, we get that there are at least $$\frac{2^{n/4}}{3n}$$ different non-terminals in the grammar.

Comment: The same proof works if $\pi_1,\pi_2 \in S_{\{0,1\}^n}$, i.e. are arbitrary permutations on the set of all $n$-bit words. Given $n/4$ bits of $\pi_i(y)$, there are exactly $2^{3n/4}$ preimages $y$.

  • $\begingroup$ Also in cstheory (due to their request): cstheory.stackexchange.com/questions/4962/…. $\endgroup$ Commented Feb 17, 2011 at 5:32
  • $\begingroup$ On cstheory you mention some unrelated tractable exceptions. I suppose by the exception $N_{\geq 1}$ you mean "at least one occurrence of terminal". Would this mean you can generate all permutations by intersecting with $\Sigma^{|\Sigma|}$? $\endgroup$
    – jerr18
    Commented Mar 7, 2011 at 17:03
  • $\begingroup$ Since $\Sigma^{|\Sigma|}$ is regular, intersecting with it does not increase the descriptive power of the grammar. So the argument still shows that it's hard to generate all permutations. $\endgroup$ Commented Mar 7, 2011 at 17:51
  • $\begingroup$ Huh???? Can you generate "at least one occurrence of terminal" in (1) REGL or (2) CFL? $\endgroup$
    – jerr18
    Commented Mar 7, 2011 at 17:59
  • $\begingroup$ I mean generate poly-size (thought your exception was this). $\endgroup$
    – jerr18
    Commented Mar 7, 2011 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .