computer-science - 入れ子と不等式を含む文脈自由文法

Question

ネストと不等式を持つ文脈自由文法の例を見つけることができませんでした。

たとえば、次の CFG を作成しようとしています。

{aibjckdl : (i < l) ^ (j < k)}

したがって、 の場合、CFG は単純に次のようになります。{aidl : (i < l)}

S -> aSd | dS | d

b と c についても同様です。しかし、2 つの文法をネストする方法がわかりません。同様の例やポインタは役に立ちます。

Answer 1

ここで私の意見では、あなたの質問に対する答えがあります：

S -> Ad | aSd | Sd
A -> Ac | c | bAc

この文法の考え方は、まず与えられた条件を満たす a と d を持つ式の一部を作成し、次に b と c の条件を満たす式を a と d の間に入れるというものです。