大门|大门-CS-2004 |问题88

考虑下面的语法G：

S → bS | aA | b
A → bA | aB
B → bB | aS | a 

设Na（w）和Nb（w）分别表示字符串w中a和b的个数。语言L（G）⊆ G生成的{a，b}+是 （A） {w|Na（w）>3Nb（w）} （B） {w|Nb（w）>3Nb（w）} （C） {w|Na（w）=3k，k∈ {0, 1, 2, …}} （D） {w|Nb（w）=3k，k∈ {0, 1, 2, …}} 答复: （C） 说明： 这里，我们有

S → bS
S → baA         (S → aA)
S → baaB     (A → aB)
S → baaa     (B → a)

因此，|Na（w）|=3。

此外，如果我们使用→ bA而不是A→ aB，

S → baA
S → babA

要终止A，我们必须使用→ 因为只有B终止于a（B→ a） 。

S → baA
S → babA
S → babaB
S → babaa

因此，这里也是，|Na（w）|=3。 所以，C是正确的选择。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验