4
$\begingroup$

Can a polynomial size CFG over large alphabet describe any of these languages:

  1. Each terminal appears $0$ or $2$ times
  2. Word repetition $\{www^* \mid w \in \Sigma^*\}$ (word repetition of an arbitrary word $w$)

"Polynomial size" Context Free Grammar is defined as Chomsky Normal Form polynomial in $|Σ|$.

References to poly-size CFGs over large alphabets will be appreciated.

EDIT: This is not a homwork. Positive answer can give extension to Restricted read twice BDDs and context free grammars

  • 0
    Crosspost in cstheory: http://cstheory.stackexchange.com/questions/3844/can-a-polynomial-size-cfg-over-large-alphabet-describe-any-of-these-languages2010-12-17

1 Answers 1