TransWikia.com

Reducing the Height of Context-Free Grammars

Theoretical Computer Science Asked by Mateus de Oliveira Oliveira on November 26, 2021

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

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.

Answered by gsv on November 26, 2021

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

Answered by user184868 on November 26, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP