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) 相等ba' 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 回答