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

Question

我试图找到生成语言的语法

L = {aibjck | j≠i + k}

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

我的第一个想法是把它分成：

L = {aibjck | j <i + k} | {aibjck | j> i + k}

即使你认为可能很明显的提示或想法也会受到高度赞赏。

Answer 1

你的方法是一个很好的方法 - 根据“不相等”中的分离将其分解为更容易的子问题，然后加入它们：

S -> L | G

现在，我们如何制作一个语法来给出一个^ i b ^ j c ^ k，其中j <i + k？我们可以从语法开始，其中j = i + k。要做到这一点，让我们把它写成^ 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。我们可以通过允许更多b D和E的规则，然后在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

Answer 2

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

L = {aibjck | j> i + k} | {aibjck | j <i + k}

首先{aibjck | j> i + k}：

将^视为空符号。

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

然后{aibjck | j <i + k}

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

结合它们只需将两者结合起来：

S -> G | L 

简单地导出和j和k，然后确定要遵循的路径G或L.我在下面编写了几个示例派生：