# Reducing the Height of Context-Free Grammars

Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.

Say that a string $w\in L(G)$ has height $h$ if $w$ has a parse-tree of height at most $h$. Say that $G$ has height $h$ if each string $w\in L(G)$ has height $h$. Let $|G|$ be the number of production rules in $G$. I have the following problem, which I believe it is well studied in the field of parallel parsing, but with a somewhat distinct terminology.

Problem: Given a context free grammar $G$ in CNF accepting a language $L(G)\subseteq \Sigma^n$, construct a context free grammar $G'$ in CNF such that

1. $L(G') = L(G)$,
2. $h(G') = O(\log n)$,
3. $|G'| = |G|^{O(1)}\cdot n^{O(1)}$.

Does the problem given above has always a solution? In other words, from $G$ we want to construct a context free grammar $G'$ accepting the same language as $G$ but such that every string in this language has a parse tree of logarithmic height. The size of the obtained grammar $G'$ is allowed to blow up polynomially in $n$ and in the size of the original CFG $G$.

I'm mostly interested in references dealing with the problem above or similar problems.

Obs 1: Without the requirement that $|G'|=|G|^{O(1)}\cdot n^{O(1)}$, we can construct a grammar $G'$ with size $2^{O(n)}$ by considering a distinct set of production rules for each string in $L(G)$.

Obs 2: I don't care about the time necessary to construct $G'$. The only important thing is its size $|G'|$.

Obs 3: Both grammars are required to be in Chomsky normal form. Also both are allowed to be ambiguous.

• The requirement that the grammars should be in Chomsky normal form is an important part of the specification of the problem. As important as the requirement that $|G'| = |G|^{O(1)} \cdot n^{O(1)}$. – Mateus de Oliveira Oliveira Feb 7 '18 at 0:16