<h2> Chomsky normal form </h2>

<p>A CFG is in CNF (Chomsky normal form) if the only productions are of the form $A \rightarrow a$ and $A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup.</p>

<p>For a grammar $G$ in CNF, we have the nice Subword Lemma: <i> If $G$ generates a word $w$, then for each $\ell \leq w$, there is a subword $x$ of $w$ of length $\ell/2 \leq |x| &lt; \ell$ which is generated by some non-terminal of $G$.</i> Proof: Descend the (binary) syntax tree, always going to the child which generates the longer subword. If you started with a subword of size at least $\ell$, you can't have gone below $\ell/2$.</p>

<h2> Solution </h2>

<p>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$.</p>

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

<p>Suppose that $p(x) = p(y)$ and $A(x) = A(y)$. Since $|s(x)|&lt;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)$.</p>

<p>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.</p>

<p>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$.</p>

<h2> More examples </h2>

<p>Using the same method, one can prove that the language where each character appears exactly twice requires exponential-size CFG in the size of the alphabet. We can replace "twice" with any subset of $\mathbb{N}$ other than four trivial ones (ignoring $0$, either containing none of $\mathbb{N}_{\geq 1}$ or all of it).</p>

<p>I would appreciate a reference for this proof method.</p>

CC BY-SA 2.5
2011-03-07T14:47:02.920Z
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|}$?
jerr18
CC BY-SA 3.0
2015-07-29T10:34:13.260Z
See related question http://cstheory.stackexchange.com/q/5014 where Yuval posted an answer with a published reference.
András Salamon
CC BY-SA 2.5
2011-02-17T03:53:39.753Z
Yuval, could you please copy the solution here also.
Kaveh
CC BY-SA 2.5
2011-02-17T12:49:13.107Z
Thank you Yuval. If your method is correct and novel I would be glad to read an article investigating more general cases with positive or negative results on polysize CFGs for finite or infinite languages.
jerr18
CC BY-SA 2.5
2011-02-17T13:33:16.763Z
There's this writeup: http://www.cs.toronto.edu/~yuvalf/cfg.pdf.
Yuval Filmus
CC BY-SA 2.5
2011-02-17T03:25:21.237Z
2011-02-17T05:27:30.943Z
2011-02-17T05:27:30.943Z
Yuval Filmus
<p>Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?</p>

<p>UPDATE: For one permutation $\pi$ it is possible. $\pi$ is the reversal or relatively minor modification of the reversal.</p>

CC BY-SA 3.0
2015-07-29T01:47:23.880Z
think this is too tersely stated without details. the "update" is not clear. what is possible? what is a "reversal" of what? by reversal do you mean a permutation reversed?
vzn
CC BY-SA 2.5
2011-02-16T17:40:22.357Z
Also asked on math.stackexchange. What he means is: Is there a sequence of permutations $\pi_1^n,\pi_2^n \in S_n$ such that the languages $L_n = \{w \pi_1(w) \pi_2(w) : w\in \{0,1\}^n\}$ have polynomial size CFGs?
Yuval Filmus
CC BY-SA 2.5
2011-02-16T21:56:58.713Z
http://math.stackexchange.com/questions/22361/do-there-exists-permutations-pi-1-pi-2-and-polynomial-size-cfg-that-describe
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-17T00:30:26.730Z
Do we know if there is a CFG for $L = \bigcup_n L_n$?
Kaveh
CC BY-SA 2.5
2011-02-17T01:49:21.093Z
@Kaveh: The answer is no, for any sequence of perms. If your language $L$ were context-free, then it has a pumping length $p$. Apply the pumping lemma for CFGs to the string in L associated to $w = 0^p 1^p$. The pumping lemma for CFGs also let's us say that, if the OQ has a positive answer, then the CFG for $L_n$ must use  at least $\Omega(n / \log n)$ variables, since we need $3n$ to be less than the pumping length, so that our CFG for $L_n$ does not accept any strings of length $> 3n$. I do not yet see how to use this to rule out a positive answer to the OQ, but it might be possible.
Joshua Grochow
CC BY-SA 2.5
2011-02-17T01:50:40.513Z
@Kaveh: (Also, if the sequence of perms can be chosen arbitrarily, then your language $L$ need not even be computable... The OQ seems to be inherently non-uniform.)
Joshua Grochow
<fl.formal-languages><grammars><context-free>
Do there exists polynomial size CFG that describe this finite language?
jerr18
# Do there exists polynomial size CFG that describe this finite language?

(Asked by: username_0 on 2011-02-16)

Do there exists permutations $\pi\_1,\pi\_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi\_1(w) \pi\_2(w)\}$ over alphabet $\{0,1\}$?

UPDATE: For one permutation $\pi$ it is possible. $\pi$ is the reversal or relatively minor modification of the reversal.

**Tags:** fl.formal-languages, grammars, context-free
> **Comments:**
> **username_2**: Also asked on math.stackexchange. What he means is: Is there a sequence of permutations $\pi_1^n,\pi_2^n \in S_n$ such that the languages $L_n = \{w \pi_1(w) \pi_2(w) : w\in \{0,1\}^n\}$ have polynomial size CFGs?  
> **username_3**: http://math.stackexchange.com/questions/22361/do-there-exists-permutations-pi-1-pi-2-and-polynomial-size-cfg-that-describe  
> **username_4**: Do we know if there is a CFG for $L = \bigcup_n L_n$?  
> **username_5**: @Kaveh: The answer is no, for any sequence of perms. If your language $L$ were context-free, then it has a pumping length $p$. Apply the pumping lemma for CFGs to the string in L associated to $w = 0^p 1^p$. The pumping lemma for CFGs also let's us say that, if the OQ has a positive answer, then the CFG for $L_n$ must use  at least $\Omega(n / \log n)$ variables, since we need $3n$ to be less than the pumping length, so that our CFG for $L_n$ does not accept any strings of length $> 3n$. I do not yet see how to use this to rule out a positive answer to the OQ, but it might be possible.  
> **username_5**: @Kaveh: (Also, if the sequence of perms can be chosen arbitrarily, then your language $L$ need not even be computable... The OQ seems to be inherently non-uniform.)  
> **username_1**: think this is too tersely stated without details. the "update" is not clear. what is possible? what is a "reversal" of what? by reversal do you mean a permutation reversed?  

---

## 1 answers

### Answer by username_2 on 2011-02-17. Score: 13

## Chomsky normal form

A CFG is in CNF (Chomsky normal form) if the only productions are of the form $A \rightarrow a$ and $A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup.

For a grammar $G$ in CNF, we have the nice Subword Lemma:  *If $G$ generates a word $w$, then for each $\ell \leq w$, there is a subword $x$ of $w$ of length $\ell/2 \leq |x| < \ell$ which is generated by some non-terminal of $G$.* Proof: Descend the (binary) syntax tree, always going to the child which generates the longer subword. If you started with a subword of size at least $\ell$, you can't have gone below $\ell/2$.

## Solution

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, 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)|

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$.

## More examples

Using the same method, one can prove that the language where each character appears exactly twice requires exponential-size CFG in the size of the alphabet. We can replace "twice" with any subset of $\mathbb{N}$ other than four trivial ones (ignoring $0$, either containing none of $\mathbb{N}\_{\geq 1}$ or all of it).

I would appreciate a reference for this proof method.

> **Comments:**
> **username_4**: Yuval, could you please copy the solution here also.  
> **username_0**: Thank you Yuval. If your method is correct and novel I would be glad to read an article investigating more general cases with positive or negative results on polysize CFGs for finite or infinite languages.  
> **username_2**: There's this writeup: http://www.cs.toronto.edu/~yuvalf/cfg.pdf.  
> **username_0**: 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|}$?  
> **username_6**: See related question http://cstheory.stackexchange.com/q/5014 where Yuval posted an answer with a published reference.  

---

