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.


2 Answers 2


The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.


In simple words, you want to inline non-terminals.
given a rule like S -> a B d, B -> b,c, you want to inline B, just replacing it with its content
means : s -> a,b,c,d what would reduce the height. You can do it only if there is no direct circular dependency in the rule, means, there is no : S -> ...S... because you can not inline that. If there is circular dependency on 2nd lvl, sutch as S-> ... B... , B -> xxxSxxx this you can inline like : S -> .... ( xxxSxxx)...

  • $\begingroup$ As mentioned in the question, the grammars should be in Chomsky normal form. I added a third observation making this requirement more explicit. $\endgroup$ Commented Feb 7, 2018 at 0:06
  • $\begingroup$ Additionally, such an inlining would blow up the number of productions exponentially in the number of prouction rules. $\endgroup$ Commented Feb 7, 2018 at 0:11
  • $\begingroup$ the Chomsky normal form seems to create unnesessary non-terminals both in height and in width, so best regards with it. If you do not have circular dependencies, you can inline the rule to the size of 1 no matter in what form it is, and if there are loops you can not change grammar to elliminate them. Yes the rules will grow in width if you replace it and if you have complex dependencies, but you do want to elliminate height? $\endgroup$
    – user184868
    Commented Feb 7, 2018 at 0:11
  • $\begingroup$ 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)}$. $\endgroup$ Commented Feb 7, 2018 at 0:16
  • $\begingroup$ ok,look example here "de.wikipedia.org/wiki/Chomsky-Normalform" see the bottom rules Xa->a, B -> b. Replace all occurences. will it be still in the Chomsky-Normalform? (sorry i m not good in "theorie". Then go upwards and try to another rules. Thats the algo i would give you. $\endgroup$
    – user184868
    Commented Feb 7, 2018 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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