context-free-grammar - 为语言创建上下文无关语法

Question

我正在上有限自动机类(class)。我正在为期中考试做准备，但在为特定语言创建语法时遇到了问题。虽然我发现简单的非常直观，但当它们变得更复杂时，我似乎不知道从哪里开始。例如:

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 |电子
X→a |

如果有人能就所涉及的思维过程给我一些指导，将不胜感激。

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 's/c 's > or < b 's)
2. 对于每个案例，首先要确保案例成立(通过强制至少一个 b 来强制 # a 的 > 比 c 的/b )然后扩展包含所有可能相等的字符串 a的/c的和b的，或更少 a的/c比 b的。
3. 对称地处理另一种情况。

问题是您需要确保生成语言中的每个字符串，并且不生成所有不属于该语言的字符串。 (重新阅读直到理解其含义)