我试过这个
C - > e（Epsilon）
S - > SASBS
S - > SBSAS
A - > a
B - > b
有人可以验证这是否正确。
你的语法是正确的。这是证明。
首先，我们证明您的语法只生成具有相同数量的a和b的字符串。请注意，在LHS上使用S的所有产品都引入与A相同数量的A。因此，从S派生的任何终端串将具有相等数量的a和b。
接下来，我们展示了使用这种语法可以导出a和b的所有字符串。我们继续使用数学归纳法。
基本情况：S - > e和S - > SASBS - > ASBS - > aSBS - > aBS - > abS - > ab和S - > SBSAS - > BSAS - > bSAS - > bAS - > baS - > ba，so语法中的三个最短字符串是由语法生成的。长度小于4的语言中没有其他字符串。
归纳假设：语言中所有长度达2k的字符串都是由语法生成的。
归纳步骤：我们必须显示语言中所有长度为2（k + 1）的字符串也是由语法生成的。如果对于某些字符串x和y，w = axb或w = bya，则x和y是语言中长度为2k的字符串，因此由语法生成。在这种情况下，我们可以使用相同的推导，额外应用S - > SASBS - > ASBS - > aSBS - > aSbS - > aSb或S - > SBSAS - > BSAS - > bSAS - > bSaS - > bSa和然后使用x或y的推导来完成推导，得到w。相反，如果w = axa或w = byb，那么x或y是一个字符串，其中b比a或b多两个b。在这种情况下，必须有一个带有| p |的w的前缀p <| w |这样p也是语言中的一个字符串（参见下面的引理）。如果前缀p是语言中的单词，并且w = pr，那么r也必须是该语言中的单词，因此w必须是L中两个单词的串联。这些单词的长度都小于| w |。所以小于2（k + 1）并由语法生成。如果它们是由语法生成的，那么它们的形式为SaSbS或SbSaS，并且可以通过使用正确顺序的产品使用语法来导出它们的串联。也就是说，S - > SASBS - > SASBSBSAS - > aSbSbSa = aSbS bSa < - aSbS SbSa（我们当然可以在最后一步反向步骤中自由选择S - > e）。