如何找到一种语言的语法，其中一个符号的重复次数不等于其他符号的总和？

Question

我正在尝试找到生成语言的语法

L = {aⁱb^jc^k | j ≠ i + k}

但是，我很难理解如何创建执行此操作的语法。我也无法在 Internet 上找到有关处理上下文无关语法中的不等式的信息。

我的第一个想法是将其拆分为：

L = {aⁱb^jc^k | j < i + k} | {aⁱb^jc^k | j > i + k}

即使是您认为显而易见的提示或想法，我们也将不胜感激。

Answer 1

通过解决这两个不等式，然后将它们组合成一个语法，我解决了这个问题。

L = {aⁱb^jc^k | j > i + k} | {aⁱb^jc^k | j < i + k}

先{aⁱb^jc^k | j > i + k}:

将 ^ 视为空符号。

G -> aA  
A -> aA | aAc | B  
B -> aB | aBb | ^

那么{aⁱb^jc^k | j < i + k}

L -> Cc  
C -> Cc | aCc | D  
D -> Db | aDb | ^

要将它们结合起来，只需将两者合并即可：

S -> G | L

要导出简单地求和 j 和 k，然后确定要遵循哪条路径 G 或 L。我在下面制定了几个示例推导：

Answer 2

您的方法很好 - 根据 "not equal" 中的析取将其分解为更简单的子问题，然后加入它们：

S -> L | G

现在，我们如何编写一个语法来给出 a^i b^j c^k 其中 j < i + k？我们可以从 j = i + k 的文法开始。为此，我们将其写为 a^i b^i b^k c^k。然后很明显这个语法有效：

L -> BC
B -> aBb | e
C -> bCc | e

现在，我们如何更改它以强制执行 j < i + k？我们必须增加 i 或 k，或两者都增加。我们可以添加 B -> aB 和 C -> Cc 以允许更多 a 和 c，但不强制执行。我们可以通过更改 L -> BC 来强制执行这两个条件中的至少一个以解决这两种可能性（为了清楚起见，我们也可以添加 L -> aBCc 但这不是必需的）。

L -> aBC | BCc
B -> aBb | aB | e
C -> bCc | Cc | e

对于G，我们以同样的方式开始：

G -> DE
D -> aDb | e
E -> bEc | e

现在，我们需要强制添加额外的b。我们可以通过为 D 和 E 允许更多的 b 规则，然后在 G 的规则中要求它来做到这一点：

G -> DbE
D -> aDb | Db | e
E -> bEc | bE | e

结合这些应该可以得到所需语言的语法：

S -> L | G
G -> DE
D -> aDb | e
E -> bEc | e
G -> DbE
D -> aDb | Db | e
E -> bEc | bE | e

如何找到一种语言的语法，其中一个符号的重复次数不等于其他符号的总和？

How to find the grammar for a language where one symbol is not repeated as many times as the sum of the others?

context-free-grammar