computation-theory - 包含相同数量的 a 和 b 的语言的 CFG

Question

我试过这个

S -> e(Epsilon)

S -> SASBS

S -> SBSAS

一个 -> 一个

乙 -> 乙

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

Answer 1

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

首先，我们证明您的语法仅生成具有相同数量 a 和 b 的字符串。请注意，LHS 上所有带有 S 的产生式引入的 A 数量与引入 B 的数量相同。因此，从 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) 的字符串也是由语法生成的。如果 w = axb 或 w = bya 对于某些字符串 x 和 y，则 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)。