3

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

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

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

4

1 回答 1

3

您列出的语言不清楚。我假设w E {a,b,c}*意味着w ε {a,b,c}*并且nb(w) != na(w) + nc(w)意味着语言中的所有字符串都有多个 b 不等于 a 的数量和 c 的数量之和。

如果是这种情况，您必须考虑该语言中所有字符串的特征，以及将字符串排除在该语言中的所有特征。

这种语言接受字符串，其中 b 的数量 =/= a 的数量 + c 的数量。我们可以将这种语言重新表述为接受以下字符串的语言：

number a's + number c's > number of b's OR number a's + number c's < number of b's

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

S1 确保至少有 1 个b(S3)，然后强制 's 的数量与 's 和 's (S0) 相等b或a' csb多于a's 和c's (S1)。S1 规则的最终结果是b's 多于a's 和c's 的字符串。

S2 确保a's 和/或c's 多于b's。它通过强制一个aor c(X) 来做到这一点，然后允许等量的a's/ c' (S0) 或更多a的 's/ c's 比b's (S2 再次)。

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

  1. 将语言表述为具体案例（a's/ c's > 或 < b's）
  2. 对于每个案例，首先确保案例将成立（通过强制至少一个来强制 #b的 > 比a's/ ）然后扩展字符串以包含所有相等的可能性's/ 's 和's , 或比 's 少's/ ' 。 cbacbacb
  3. 对称处理另一种情况。

问题是您需要确保生成该语言中的每个字符串，并且不生成所有不在该语言中的字符串。 （重新阅读，直到它的含义下沉）

于 2010-11-16T19:00:45.660 回答