1
$\begingroup$

I'm trying to find sup of $\|\mathbb{G}\|$ where $\mathbb{G}$ is CFG in Chomsky Normal Form. So far i have done some work, but I'm really not sure in my proof. Let $G = \langle Q, N, S, R\rangle$ and $$\alpha \rightarrow \beta \in R,\ |\beta| = n$$ $$\|\alpha\| \le \sum_{i=0}^{\log_{2}n}2^{n}\,.$$ I made this conclusion by observing the binary tree I get when I try substituting the right side of the rule with $$\beta =b_{1}b_{2}...b_{n}$$ $$\beta \rightarrow A_{1}A_{2},A_{1}\rightarrow B_{1}B_{2}, A_{2}\rightarrow B_{3}B_{4}$$ and so on until $$Q_{1} \rightarrow b_{1}b_{2}, ...,Q_{[\frac{n}{2}]}\rightarrow b_{n-1}b_{n}$$

The result is binary tree with height $\log_{2}n$ which on each level has $2^{i}, i = {0,1,...,\log_{2}n}$ nodes. Finally I claim that $$\|\mathbb{G}\| \le |N| + |N|\sum_{i=0}^{|N|-1}(\|\alpha\|),\ \exists (A \rightarrow \alpha) \in R\,.$$

$\endgroup$
  • $\begingroup$ It would probably help to spell out "CNF" in the title at least because everyone will assume you mean conjunctive normal form Boolean formulas. $\endgroup$ – David Richerby Jun 29 '17 at 14:50
  • $\begingroup$ Oh, i really didn't mean that. Thank you! $\endgroup$ – Zarrie Jun 29 '17 at 15:49
1
$\begingroup$

It is well-known, and stated in Wikipedia (which gives a reference: Lange and Leiß), that there is an algorithm transforming an arbitrary context-free grammar $G$ into a grammar in Chomsky normal form of size $O(|G|^2)$.

The following grammar might be an example showing that the quadratic blow-up is necessary: $$ \begin{align*} &S \to A_1 \ldots A_m \\ &A_1 \to A_2 \mid \sigma_1 \\ &A_2 \to A_3 \mid \sigma_2 \\ &\cdots \\ &A_{m-1} \to A_m \mid \sigma_{m-1} \\ &A_m \to \sigma_m \end{align*} $$ This grammar has size $\Theta(m)$, and it seems that every grammar in Chomsky normal form for this language must have size $\Omega(m^2)$.

$\endgroup$

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.