automata - 我想做一个 CFG，其中字母 b 永远不会三倍

Question

需要有关上下文无关语法的帮助。我想要一个字母 b 永远不会增加三倍的 cfg。这意味着没有单词包含子字符串 bbb。语言只包含字母 {a,b}

标签： automatacg

Answer 1

这是该语言的一个有用的递归定义：

• 空字符串是语言
• b 在语言中
• bb 在语言中
• 如果 x 是语言中的字符串，则 xa 是语言中的字符串
• 如果 x 是语言中的字符串，则 xab 是语言中的字符串
• 如果 x 是语言中的字符串，则 xabb 是语言中的字符串
• 除非符合上述规则，否则该语言中没有其他内容

首先，让我们确保这个定义是正确的。不难争辩说，这个定义定义了必须是我们的目标语言的字符串；没有子字符串 bbb 的字符串可以满足上述规则。定义是否涵盖所有情况，以便所有没有子字符串 bbb 的字符串都可以工作？事实上，它必须。考虑语言中的任何字符串。它要么长度小于 3（在这种情况下，我们可以检查所有可能的字符串都被正确处理，它们是）；对于较长的字符串，它们必须以 a、ab 或 abb 结尾（它们不能以 bbb 结尾）。我们的规则意味着在没有这些后缀的语言中存在字符串 x，可以递归地检查其成员资格。这可以通过数学归纳得到一个令人信服的证明。

有了上面这样的递归定义，我们就可以写下相应的语法：

S -> e | b | bb | Sa | Sab | Sabb

这里真正的独创性在于获得定义。我是怎么做到的？我想到了语言中最短的字符串——独特的、不符合模式的字符串——然后我问如何用较短的字符串制作更长的字符串。也就是说，给定语言中的一个字符串，如何使一个更大？这就是上下文无关语法让我们做的关键。