context-free-grammar - 具有某些不等式的上下文无关语法

Question

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

我想知道遵循 CFG 的正确性-

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

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

请帮忙

Answer 1

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

L _a = { a ⁱ } -> ε | L _a a
L _ab = { a ⁱ b ⁱ } -> ε | 一个实验室_{_} _

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

S -> a L _a L _ab L _ba L _a | 啦啦啦啦_啦啦啦啦_{啦啦_} _ _{_} _

现在这个语法是模棱两可的，所以如果你关心那种东西，你可以重构它以消除（或至少减少）歧义，但这是另一个问题。