为语言创建无上下文语法

Question

我正在学习有限自动机课程，为期中考试做准备时，我在为特定语言创建文法方面遇到了困难。虽然我发现简单的文法非常直观，但当它们变得更加复杂时，我不知道从哪里开始。例如：

L = { w E { a,b,c}* : nb(w) != na(w) + nc(w) }

答案是：

S→S1 | S2 S1→bS3 | S3b | S3bS3 S3→S0 | S1 S2→XS4 | S4X | S4XS4 S4→S | S2 S0→bS0XS0 | XS0bS0 | e X→a | c

如果有人能在思维过程上给我一点指导，我将不胜感激。

- PhilT

Answer 1

您提供的语言不够清晰。我假设w E {a,b,c}*的意思是w ε {a,b,c}*，而nb(w) != na(w) + nc(w)的意思是该语言中所有字符串的字母b的数量不等于字母a和字母c的数量之和。

如果是这样的话，您需要考虑将在该语言中的所有字符串的特征以及排除一个字符串不属于此语言的所有特征。

该语言接受的字符串满足字母b的数量不等于字母a和字母c的数量之和。我们可以将这种语言重新表述为接受以下字符串： 字母a的数量+字母c的数量 > 字母b的数量 或 字母a的数量+字母c的数量 < 字母b的数量

这解释了第一个S--> S1 | S2

S1确保至少有1个字母b（S3），然后强制要求字母b的数量等于字母a和字母c的数量（S0）或字母b的数量大于字母a和字母c的数量（S1）。 S1规则的净结果是一个具有更多字母b的字符串，而不是字母a和字母c。

S2确保有更多的字母a和/或字母c比字母b。它通过强制出现字母a或字母c（X），然后允许相等数量的字母a/字母c（S0）或字母a/字母c的数量大于字母b（再次S2）。

这是针对您的示例特定的，但您可以看到创建此语法所需的思考过程：

1.将语言制定为具体情况（字母a/字母c > 或 < 字母b） 2.对于每种情况，首先确保该情况成立（通过强制至少一个字母b来强制#字母b > 字母a / 字母c），然后将字符串扩展为包括所有相等的字母a / 字母c和字母b或字母a / 字母c少于字母b的可能性。 3.对称处理其他情况。

问题在于您需要确保生成语言中的每个字符串，并且不生成不属于该语言的所有字符串。（反复阅读此内容，直到其含义深入人心）

- prelic