4
$\begingroup$

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$

  • 0
    You mean a polysize CFG for $L_n = \{w\pi_1(w)\pi_2(w) : w \in \{0,1\}^n\}$?2011-02-16
  • 0
    Also asked on cstheory.2011-02-16
  • 0
    You really need a sequence of permutations $\pi_1^n,\pi_2^n$, one of each possible size.2011-02-16
  • 0
    The only way to describe such a language with a CFG is by enumerating its words, there is really nothing good you can do.2011-02-16
  • 0
    @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.2011-02-17
  • 0
    Link in cstheory: http://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language.2011-02-17

1 Answers 1