我想设计一个上下文无关文法下列语言：上下文无关文法平衡parethesis
L = {宽E {（，）} * | w为平衡}
我提出以下语法：
的S - >（S）S | Ë
而在演讲中提出的解决方案是：
的S - >（S）| SS | E
我无法弄清楚，我的解决方案有什么问题。 我跑无论对于各种情况，如语法：
（（）（）），（）（）（），和（（））（）
并且两个CFG接受这些字符串。
有人可以请帮忙，我的CFG不会涵盖什么情况。或者它们都是等价的。或者达到最终状态所需的转换次数是不同的。
这两种语法都生成相同的语言，所以都不正确。
我更喜欢你的，因为它是明确的，但这不是要求的一部分。许多人似乎发现其他答案更容易理解，但这也不是要求的一部分，它是一个非常主观的标准。
rici是正确的。为了显示语法是相同的（它们生成相同的语言），可以显示出一个能够复制另一个，从而生成相同的字符串。
例如，所提出的语法可以产生(S)S和E如下：
`S => SS => (S)S` and `S => E`.
你的语法可以复制其他语法如下：
`S => (S)S => (S)`
`S => E`
对于S => SS，你不能真正复制那个，或者讲课中的语法可以的任何其他S^n。没关系，因为你不需要覆盖所有这些，只要覆盖一串串终端即可。对于这一个，注意S^n最终必须所有的S变成(S)（其它规则），然后从左边工作：
`S => (S)S => (S)(S)S => ... => (S)^n S => (S)^n`
现在你做。你可以通过以下方式来证明它：（a）你的语法生成的每个字符串都在L; （b）如果一个字符串在L那么你的语法生成它。您可以通过归纳法（例如，括号对的数量）来完成此操作。
基本情况：对于n = 0，字符串是E，这在L。 n = 0唯一的字符串是E，它是由我们的语法生成的。
归纳假设：所有的字符串与直到并包括k双通过我们的语法生成的括号是L，并在L所有字符串与直到并包括k对括号通过我们的语法生成。
归纳步：我们显示出与k+1对我们的语法产生括号的所有字符串都在L，并且在L与k+1对括号的所有字符串由我们的语法生成。
假设串w与通过使用规则S => (S)S我们的语法生成k+1对括号。然后w =（X）Y where X andare words inÝ大号with fewer than K + 1pairs of parentheses. But then they are balanced by the induction hypothesis.瓦特is therefore balanced since X is balanced, thus（X）is balanced and（X）Y = w`过。
假设字符串w与k+1括号对在L。然后，通过L的定义，w是平衡的。平衡括号的字符串必须具有相同数量的左右括号，并且在任何前缀中必须至少具有与右括号相同数量的左括号（因此它们在任何后缀中必须至少具有与左括号一样多的右括号）。选择第一个左括号和第一个右括号，以便前缀包含相等数目的左右括号;这是w的子串(x)。在子字符串之后，还必须具有与右括号相同数量的左括号，并且在任何前缀中必须至少有与右括号一样多的左括号（这是为了满足w平衡的条件）。因此，之后会发生什么 - 我们称之为y - 也必须是一个平衡的括号字符串。作为（正确的）子字符串，x和y必须短于w（包含更少的括号对），它们必须均衡，因此两者都在L中。但它们都是由语法生成的，而且由于语法包含生产S => (S)S，因此语法生成(x)y。
QED
你的答案好感谢。 – yogeshagr