context-free-grammar - 上下文无关文法的构建

Question

所以，我有这种语言L={a^i b^2j+1 / i<>j}，我必须基于它生成一个上下文无关的语法，你能帮我说明一下这样做的步骤吗？

到目前为止，我有这个：

    S-->aS/aBbb
    B-->bB/b/e(empty)

但我不确定它是否正确，请帮助我理解它。

Answer 1

对于具有“不相等”限制的语言，最简单的方法通常是首先找到与具有“相等”限制的语言相对应的语法，然后将其更改为需要更多的东西。

在这种情况下，我们有许多a令牌，然后是奇数个b令牌，其中约束是每个令牌的数量。对于相同的情况，这变得公正

S → aSbb | b

一个b具有相同数量的as 和b围绕它的 s 对的单个。

为了使其不相等，我们需要添加额外a的 s 或额外的Bs 对，但不能同时添加：

S → AS' | S'B
S' → aS'bb | b
A → Aa | a
B → Bbb | bb