モナドCFTGで生成できない文脈自由木言語の例

文脈自由木文法(CFTL)によって生成された文脈自由な木言語(CFTL)であると仮定して、私はモナドによって生成されないCFTLの例を探していますCFTG(MCFTG)。

言い換えれば、同等の(MCFTG)を構築することが不可能な非モナド的なCFTGを探しています。

論文に存在するCFTGのすべての例は、本質的にモナドCFTGです。

私はまだ自分でこのような文法を作ろうとしています。しかし、誰かが既にそのような例を知っているかもしれないし、答えとしてそれを共有することができます。私はどんな助けにも深く感謝します。

ベストアンサー

Michael
Wehar
のコメントに基づいて、私はこの文法が同等のMCFTGを持っている:

$ S rightarrow T(a、a)$

$ T(x_1、x_2) rightarrow T(b(x_1、x_2)、c(x_1、x_2))$

$ T(x_1、x_2) rightarrow a(x_1、x_2)$

この文法は完全なバイナリツリーを生成します。各ブランチでは、左の子はリーフの場合は a
というラベルを持ち、それ以外の場合は b というラベルを持ちます。右の子は葉であれば
a というラベルを持ち、そうでなければ c というラベルを持ちます。

私はこの事実を非常に厳密に証明していませんが、ここではいくつかの観察があります。

それは、木の同じ言語を生成するような文脈自由な木文法を構築することが不可能になります。これは、単一ランクの非端末が親ノードのラベル(
b または c
)を正しく設定できないためです。このラベルは、「コンテキスト」に依存します。このノードは、ノードが残っているか、それとも正しいかに関する知識です。

また、与えられたツリーの各パスの深度は同じであるため、独立した非終端記号によって次の各ブランチが生成される文法では生成できません。

返信を残す

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