设计上下文无关语法 [HW]

Question

我已经为此花费了大约 5 个小时的家庭作业，我希望你们中的一些人能够提供帮助，因为 CFG 是 CS 的重要组成部分。

我真正的麻烦是 C 部分。

为以下每种语言设计一个 CFG：

A. {(a^i)(b^j)(c^k)} WHERE (i != j) AND i,j,k >= 0)

我想出了：

Start-> aAB | AbB
A-> epsilon | aA
B-> epsilon | C | bB
C-> epsilon | cC

这似乎适用于 bccc、abbcc、aabbb、cc，所以我认为我在这里很好。

B. {(a^i)(b^j)(c^k)} WHERE (i != k) AND i,j,k >= 0)

Start-> aABC | ABcC
A-> epsilon | aA
B-> epsilon | bB
C-> epsilon | cC

这适用于 bc, bbcc, ab, abb, aac 所以当 i!=k

C. {(a^i)(b^j)(c^k)} WHERE (i != j OR i != k) AND i,j,k >= 0 时，一切看起来都很好）

Start-> aABC | AbB | ABcC
A-> epsilon | aA
B-> epsilon | bB | C
C-> epsilon | cC

我不认为C部分是正确的，但我相信A和B部分是正确的。谁能告诉我我是对/错还是提供帮助？我相信，在最后一种情况下，我只是做一个 OR，并且因为我的 A、B、C 变量几乎相同，所以我可以通过组合来逃脱。它似乎像 bc 、 acc 和其他许多东西一样工作，但我感觉我不应该简单地组合开始状态。

有人知道我是否正确或接近或有任何提示吗？

Answer 1

请记住，当您测试语法时，请确保还使用应被拒绝的字符串进行测试（有关当前对您而言失败的一些字符串，请参阅 @Paulo 的答案）。要解决前两个问题，请编写一个表示 A^i B^j 的语法，其中 i != j;将任意数量的 c 的语法添加到第 1 部分的末尾，并将该语法添加到第 2 部分的中间。对于第 3 部分，请记住两个语法的并集可以很容易写成语法。

Answer 2

您的第一个语法与 abc 匹配（通过 Start -> AbB -> abB -> abC -> abc），因此它不是正确的语法。

因此，您需要确保以相同的数量创建 a 和 b（然后为其中一个创建更多数量）。

同样的 abc 也与您的第二条规则相匹配，但它也不应该被允许。