包含相等数量的 a 和 b 的语言 CFG
CFG of Language which contains equal # of a's and b's
我试过了
S -> e(Epsilon)
S -> SASBS
S -> SBSAS
A -> 一个
B -> b
谁能验证这是否正确。
你的语法是正确的。这是证明。
首先，我们证明您的语法只生成 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 在最后的反向步骤证明中）。
我试过了
S -> e(Epsilon)
S -> SASBS
S -> SBSAS
A -> 一个
B -> b
谁能验证这是否正确。
你的语法是正确的。这是证明。
首先，我们证明您的语法只生成 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 在最后的反向步骤证明中）。