所以这里有一个语法R和一个Langauge L，我想证明从R出来的是L。

可能你想做的就是证明某种语法R的语言L（R）与另一种以其他方式指定的其他语言L相同（在你的情况下，是带有正则表达式的set-builder表示法）。

所以我想证明L（G）⊆L和L（G）⊇L是正确的。

鉴于以上假设，你认为这是进行证明的正确方法是正确的。

对于L（G）⊆L：通过归纳表示导数阶数i，我发现在每个导数阶u→w之后，w根据R的规则从u产生w，w = v1v2或w = v1v2w，其中|为|。v2 | = | v1 | 和v1∈{a} ∗和v2∈{b} ∗。并在感应开始时：在i = 0时，得出w为ε，在i = 1时，w为{ε，abS}。

这对我来说很难。并不是说这是错误的。让我用自己的话写下来，也许你或其他人可以判断我们是否在说同样的话。

我们想要证明L（R）是L的子集。也就是说，语法R生成的任何字符串都包含在语言L中。我们可以通过对生成的字符串推导的步骤数进行数学归纳来证明这一点。通过语法。我们从一个推导步骤的基本情况开始：S-> e通过选择n = 0产生空词，它是语言L中的字符串。现在，我们已经建立了基本情况，我们可以陈述归纳假设：假设对于从语法直到k并包括k的多个步骤中的所有字符串，这些字符串也位于L中。现在我们必须证明归纳步骤：从k +1步骤中从语法中得出的任何字符串也位于L.令w为从语法中以k + 1个步长派生的任何字符串。从语法上很明显，w的推导必须是S-> abS-> ababS-> ... -> abab ... abS-> abab ... abe = abab ... ab。但是，这种派生与以k个步长从语法派生字符串相同，只是在应用S-> e之前有一个额外的应用S-> abS。通过归纳假设，我们知道以k步导出的字符串w'的形式（ab）^ m，对于m至少为零，并且在推导中加上S-> abS的额外应用会增加ab。因为（ab）^ m（ab）=（ab）^（m + 1），所以我们可以选择n = m + 1。因此，根据需要，以k + 1步从语法派生的所有字符串也都使用该语言。通过归纳假设，我们知道以k步导出的字符串w'的形式（ab）^ m，对于m至少为零，并且在推导中加上S-> abS的额外应用会增加ab。因为（ab）^ m（ab）=（ab）^（m + 1），所以我们可以选择n = m + 1。因此，根据需要，以k + 1步从语法派生的所有字符串也都使用该语言。通过归纳假设，我们知道以k步导出的字符串w'的形式（ab）^ m，对于m至少为零，并且在推导中加上S-> abS的额外应用会增加ab。因为（ab）^ m（ab）=（ab）^（m + 1），所以我们可以选择n = m + 1。因此，根据需要，以k + 1步从语法派生的所有字符串也都使用该语言。

为了证明该语言中的所有字符串都可以从语法中导出，请考虑以下构造：要导出语法中的字符串（ab）^ n，将产生式S-> abS应用等于n的次数，然后将生产S-> e恰好一次。第一步给出中间形式（ab）^ n，第二步给出闭合形式的字符串（ab）^ n。