<p>The partial case is presented here: <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309493/" rel="nofollow noreferrer">Balancing Straight-Line Programs for Strings and Trees</a>. I'm not sure, that the problem can be solved in the general case.</p>

CC BY-SA 4.0
2020-07-22T14:10:46.650Z
2020-07-22T14:10:46.650Z
gsv
<p>In simple words, you want to inline non-terminals.<br>
given a rule like S -> a B d, B -> b,c, you want to inline B, just replacing it with its content<br> 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)...</p>

CC BY-SA 3.0
2018-02-07T00:06:00.293Z
As mentioned in the question, the grammars should be in Chomsky normal form. I added a third observation making this requirement more explicit.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2018-02-07T00:11:39.487Z
Additionally, such an inlining would blow up the number of productions exponentially in the number of prouction rules.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2018-02-07T00:11:47.180Z
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?
user184868
CC BY-SA 3.0
2018-02-07T00:16:57.937Z
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
CC BY-SA 3.0
2018-02-07T00:21:33.743Z
ok,look example here "https://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.
user184868
CC BY-SA 3.0
2018-02-06T23:56:59.047Z
2018-02-06T23:56:59.047Z
user184868
<p>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$. </p>

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

<p><strong>Problem:</strong> 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</p>

<ol>
<li>$L(G') = L(G)$,</li>
<li>$h(G') = O(\log n)$, </li>
<li>$|G'| = |G|^{O(1)}\cdot n^{O(1)}$.  </li>
</ol>

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

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

<p><strong>Obs 1:</strong> 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)$. </p>

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

<p><strong>Obs 3:</strong> Both grammars are required to be in Chomsky normal form. Also both are allowed to be ambiguous.</p>

<reference-request><context-free><parsing>
Reducing the Height of Context-Free Grammars
Mateus de Oliveira Oliveira
# Reducing the Height of Context-Free Grammars

(Asked by: username_0 on 2018-02-06)

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.

**Tags:** reference-request, context-free, parsing


---

## 2 answers

### Answer by username_1 on 2020-07-22. Score: 2

The partial case is presented here: [Balancing Straight-Line Programs for Strings and Trees](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309493/). I'm not sure, that the problem can be solved in the general case.


---

### Answer by username_2 on 2018-02-06. Score: -5

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

> **Comments:**
> **username_0**: As mentioned in the question, the grammars should be in Chomsky normal form. I added a third observation making this requirement more explicit.  
> **username_0**: Additionally, such an inlining would blow up the number of productions exponentially in the number of prouction rules.  
> **username_2**: 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?  
> **username_0**: 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)}$.  
> **username_2**: ok,look example here "https://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.  

---

