Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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* | 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

share|improve this question
    
Crosspost in cstheory: cstheory.stackexchange.com/questions/3844/… –  jerr18 Dec 17 '10 at 11:46
add comment

1 Answer 1

The language described in (2) is not context free. Take the word $a^nba^nba^nb$ for $n$ large enough, and use the pumping lemma to get a word not in the language.

As for (1), consider a grammar in CNF (Chomsky Normal Form) generating that language. Let $n = |\Sigma|$. Consider all $S=(2n)!/2^n$ saturated words containing each character twice. Looking at the tree generating each of these words $w$, there must be a symbol $A_w$ which generates a subword $s_w$ of length between $1/3$ of $2/3$ of the entire word (of length $2n$). Suppose $A_u = A_v$. Then $|s_u| = |s_v|$ and $s_u = s_v$ up to permutation, since otherwise we can replace one occurrence by the other to get a word not in the language.

How many times can a given $A_u$ appear? Equivalently, in how many saturated words does $s_u$ appear, up to permutation, somewhere in the word? Any such word can be obtained from $u$ by permuting $s_u$, permuting the rest of the word, any rotating the result, to a total of $2n|s_u|!(2n-|s_u|)! \leq 2n(2n/3)!(4n/3)!$. Therefore the number of different symbols in the language is at least $$ \frac{(2n)!/2^n}{2n(2n/3)!(4n/3)!} = O\left(\frac{c^n}{n^{1.5}}\right),$$ where $c = 9/4\sqrt[3]{2} \approx 1.78583$ (asymptotics courtesy of Wolfram Alpha).

According to Wikipedia, one can transform a grammar $G$ into a CNF grammar of size $O(|G|^2)$. Therefore this language requires exponentially many symbols for any grammar.

share|improve this answer
    
Thank you. Before accepting I will need some time. –  jerr18 Dec 21 '10 at 10:07
    
For an alternative proof, see math.stackexchange.com/questions/14311/…. –  Yuval Filmus Dec 25 '10 at 4:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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