为相同数量的 "a" 和 "b" 文法寻找等效的 LR 文法？
Finding an equivalent LR grammar for the same number of "a" and "b" grammar?
我似乎无法找到等效的 LR 语法：
S → aSbS | bSaS | ε
我认为识别的字符串中 'a' 的数量与 'b'.
相同
对此有什么解决方法？是否可以为此找到和LR语法？
提前致谢！
编辑：
我找到了我认为是等价的语法，但我无法证明它。
我觉得需要先证明原文法生成上面的语言，再证明下面的等价文法生成语言。但我不知道该怎么做。我应该怎么做？
S → ABS |巴斯 | ε
乙→乙| aBB
一个→一个| bAA
提前致谢...
PS: 我已经证明了这个新文法是LL(1), SLR(1), LR(1) and LALR(1).
除非一个文法与另一个文法直接相关——例如通过规范化、空产生消除等标准转换——在不知道是什么的情况下证明两个文法派生出相同的语言是非常困难的语言群岛通常更容易证明（独立地）每个文法都派生出语言。
您提供的第一个语法：
S → aSbS | bSaS | ε
实际上确实导出了字母表中所有字符串的语言 {a, b}<sup>*</sup> 其中 as与bs的个数相同。我们可以分两部分来证明：第一，每个被文法识别的句子都有属性，第二，每个有属性的句子都可以由那个文法推导出来。两种证明都是通过归纳法进行的。
对于前向证明，我们通过推导数进行归纳。假设我们有一些推导 S → α → β → … → ω，其中所有希腊字母代表非终结符和终结符的序列。
如果推导的长度恰好为零，因此它以 S 开始和结束，那么任何派生句子中都没有终结符，因此很明显每个派生句子都有相同数量的 as 和 bs。 （基础步骤）
现在进行归纳步骤。假设已知每个长度为 i 的推导都以一个派生句子结尾，该句子具有相同数量的 as 和 bs .我们想从这个前提证明，每个长度 i+1 的推导都以一个句子结束，该句子具有相同数量的 as 和 bs。但这也很清楚：三个可能的生产步骤中的每一个都保持奇偶校验。
现在，让我们反方向看一下：每一个a和b个数相同的句子都可以推导出来那个语法。我们将通过归纳字符串的长度来做到这一点。我们的归纳前提是，如果对于每个 j ≤ i，每个句子都恰好 j as 和 j bs 是从 S 派生出来的，那么每个句子都恰好 i+1 as 和 i+1 bs。 （这里我们只考虑仅由终结符组成的句子。）
考虑这样一句话。它以 a 或 b 开头。假设它以一个a开头：那么句子中至少有一个b使得以结尾的前缀b 每个终端的编号相同。 （将字符串想象成沿着方形网格行走：每个 a 沿对角线向上和向右移动一个单位，并且每个 b 沿对角线向下移动一个单位对。由于端点与起点的高度完全相同，并且图中没有虫洞，所以一旦我们上升，我们迟早要下降到起始高度，这是一个以 b 结尾的前缀.) 因此该前缀的内部（除了开头的 a 和结尾的 b 之外的所有内容）是平衡的，字符串的其余部分也是如此。两者都较短，因此通过归纳假设可以从 S 推导出它们。进行这些替换，我们得到 aSbS ，可以从 S 推导出来。相同的参数适用于以 b 开头的字符串。同样，基础步骤很简单。
所以这基本上就是您需要适应语法的证明过程。
祝你好运。
顺便说一下，这类问题也可以在 cs.stackexchange.com 或 math.stackexchange.com 上提出，那里有 MathJax。 MathJax 使编写数学证明变得不那么乏味，因此您很可能会发现您会在那里获得更易读的答案。
我似乎无法找到等效的 LR 语法：
S → aSbS | bSaS | ε
我认为识别的字符串中 'a' 的数量与 'b'.
相同对此有什么解决方法？是否可以为此找到和LR语法？
提前致谢！
编辑：
我找到了我认为是等价的语法，但我无法证明它。
我觉得需要先证明原文法生成上面的语言，再证明下面的等价文法生成语言。但我不知道该怎么做。我应该怎么做？
S → ABS |巴斯 | ε
乙→乙| aBB
一个→一个| bAA
提前致谢...
PS: 我已经证明了这个新文法是LL(1), SLR(1), LR(1) and LALR(1).
除非一个文法与另一个文法直接相关——例如通过规范化、空产生消除等标准转换——在不知道是什么的情况下证明两个文法派生出相同的语言是非常困难的语言群岛通常更容易证明（独立地）每个文法都派生出语言。
您提供的第一个语法：
S → aSbS | bSaS | ε
实际上确实导出了字母表中所有字符串的语言 {a, b}<sup>*</sup> 其中 as与bs的个数相同。我们可以分两部分来证明：第一，每个被文法识别的句子都有属性，第二，每个有属性的句子都可以由那个文法推导出来。两种证明都是通过归纳法进行的。
对于前向证明，我们通过推导数进行归纳。假设我们有一些推导 S → α → β → … → ω，其中所有希腊字母代表非终结符和终结符的序列。
如果推导的长度恰好为零，因此它以 S 开始和结束，那么任何派生句子中都没有终结符，因此很明显每个派生句子都有相同数量的 as 和 bs。 （基础步骤）
现在进行归纳步骤。假设已知每个长度为 i 的推导都以一个派生句子结尾，该句子具有相同数量的 as 和 bs .我们想从这个前提证明，每个长度 i+1 的推导都以一个句子结束，该句子具有相同数量的 as 和 bs。但这也很清楚：三个可能的生产步骤中的每一个都保持奇偶校验。
现在，让我们反方向看一下：每一个a和b个数相同的句子都可以推导出来那个语法。我们将通过归纳字符串的长度来做到这一点。我们的归纳前提是，如果对于每个 j ≤ i，每个句子都恰好 j as 和 j bs 是从 S 派生出来的，那么每个句子都恰好 i+1 as 和 i+1 bs。 （这里我们只考虑仅由终结符组成的句子。）
考虑这样一句话。它以 a 或 b 开头。假设它以一个a开头：那么句子中至少有一个b使得以结尾的前缀b 每个终端的编号相同。 （将字符串想象成沿着方形网格行走：每个 a 沿对角线向上和向右移动一个单位，并且每个 b 沿对角线向下移动一个单位对。由于端点与起点的高度完全相同，并且图中没有虫洞，所以一旦我们上升，我们迟早要下降到起始高度，这是一个以 b 结尾的前缀.) 因此该前缀的内部（除了开头的 a 和结尾的 b 之外的所有内容）是平衡的，字符串的其余部分也是如此。两者都较短，因此通过归纳假设可以从 S 推导出它们。进行这些替换，我们得到 aSbS ，可以从 S 推导出来。相同的参数适用于以 b 开头的字符串。同样，基础步骤很简单。
所以这基本上就是您需要适应语法的证明过程。
祝你好运。
顺便说一下，这类问题也可以在 cs.stackexchange.com 或 math.stackexchange.com 上提出，那里有 MathJax。 MathJax 使编写数学证明变得不那么乏味，因此您很可能会发现您会在那里获得更易读的答案。