您列出的语言不清楚。我假设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
' c
sb
多于a
's 和c
's (S1)。S1 规则的最终结果是b
's 多于a
's 和c
's 的字符串。
S2 确保a
's 和/或c
's 多于b
's。它通过强制一个a
or c
(X) 来做到这一点,然后允许等量的a
's/ c
' (S0) 或更多a
的 's/ c
's 比b
's (S2 再次)。
这是特定于您的示例的,但您可以看到创建此语法的思考过程:
- 将语言表述为具体案例(
a
's/ c
's > 或 < b
's)
- 对于每个案例,首先确保案例将成立(通过强制至少一个来强制 #
b
的 > 比a
's/ )然后扩展字符串以包含所有相等的可能性's/ 's 和's , 或比 's 少's/ ' 。 c
b
a
c
b
a
c
b
- 对称处理另一种情况。
问题是您需要确保生成该语言中的每个字符串,并且不生成所有不在该语言中的字符串。 (重新阅读,直到它的含义下沉)