包含相等数量的 a 和 b 的语言 CFG

Question

我试过这个

S -> e(Epsilon)

S -> SASBS

S -> SBSAS

一个->一个

B -> b

有人可以验证这是否正确。

Answer 1

你的语法是正确的。这是证据。

首先，我们证明您的语法仅生成具有相同数量的 a 和 b 的字符串。请注意，LHS 上带有 S 的所有产生式都会引入与 B 相同数量的 A。因此，从 S 派生的任何终结符串都将具有相同数量的 a 和 b。

接下来，我们证明可以使用此语法导出 a 和 b 的所有字符串。我们继续使用数学归纳法。

基本情况：S -> e 和 S -> SASBS -> ASBS -> aSBS -> aBS -> abS -> ab 和 S -> SBSAS -> BSAS -> bSAS -> bAS -> baS -> ba，所以语言中的三个最短字符串是由语法生成的。该语言中没有其他长度小于 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 多两个，或者 a 比 b 多两个。在这种情况下，w 必须有一个带有 |p| 的前缀 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）。