具有某些不等式的上下文无关文法

Question

语言 L= {a^i b^j a^k | 的正确上下文无关语法是什么？ j< i + k} ?

我想知道下面这个CFG的正确性-

S-> aaSbA | A | ^
A-> bAa | a

是否有任何标准规则来获取满足 j < i + k 的字符串？

请帮忙

Answer 1

通常的方法是将其分解为更简单的语言。从简单的重复语言开始：

L_a = { aⁱ } -> ε | L_aa
L_ab = { aⁱbⁱ } - > ε | aL_abb

现在您可以使用这些来构建您的语言。你语言的核心是L_abL_ba .这给你相同的模式，但 j = i + k。所以要得到 <，你需要在之前或之后至少添加一个 a。所以你最终得到

S -> aL_aL_abL_baL_a | L_aL_abL _baL_aa

现在这个语法有歧义，所以如果你关心这类事情，你可以重构它以消除（或至少减少）歧义，但这是另一个问题。