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$ – Yuval Filmus Feb 16 '11 at 17:34
  • $\begingroup$ Also asked on cstheory. $\endgroup$ – Yuval Filmus Feb 16 '11 at 17:40
  • $\begingroup$ You really need a sequence of permutations $\pi_1^n,\pi_2^n$, one of each possible size. $\endgroup$ – Yuval Filmus Feb 16 '11 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 Feb 16 '11 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$ – Yuval Filmus Feb 17 '11 at 3:20

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$ – Yuval Filmus Feb 17 '11 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 Mar 7 '11 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$ – Yuval Filmus Mar 7 '11 at 17:51
  • $\begingroup$ Huh???? Can you generate "at least one occurrence of terminal" in (1) REGL or (2) CFL? $\endgroup$ – jerr18 Mar 7 '11 at 17:59
  • $\begingroup$ I mean generate poly-size (thought your exception was this). $\endgroup$ – jerr18 Mar 7 '11 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.