文脈自由文法の高さの低減

言語$ L(G) subseteq Sigma ^ n $を持つチョムスキー正規形(CNF)では、$ G
$を文脈自由文法とする。つまり、すべての文字列は$ G $によって生成され、サイズは$ n $です。

L(G)$の文字列$ w が高さ$ h $の解析木を持つ場合、高さ$ h $を持つとします。 L(G)$の各文字列$ w
に高さ$ h $がある場合、$ G $に高さ$ h $があるとします。 $ G | $を$ G
$の生産規則の数とする。私は次の問題を抱えています。パラレル解析の分野では十分に研究されていると思いますが、多少の違いはあります。

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)} $。

上記の問題は常に解決策がありますか? 言い換えると、$ G $から文脈自由文法$ G ‘$を$ G
$と同じ言語を受け取りたいが、この言語のすべての文字列は対数の高さの解析木を持つようにしたい。得られた文法$ G ‘$の大きさは、$
n $と元のCFG $ G $の大きさで多項式で爆破することができます。

私は主に、上記の問題や同様の問題を扱っている参考文献に興味があります。

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.

ベストアンサー

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

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です