证明一种语言是语法的一部分，反之亦然
proving that a language is part of a grammar and vice versa
所以这里有语法R和语言L，我想证明从R出来L。
R={S→abS|ε} , L={(ab)n|n≥0}
所以我想我会证明 L(G) ⊆ L 和 L(G) ⊇ L 是正确的。
对于 L (G) ⊆ L：我通过对导数步骤 i 的归纳表明，在每个导数步骤 u → w 之后，w 根据 R 的规则从 u 中得出，w = v1v2 或 w = v1v2w 与 | v2 | = | v1 | v1 ∈ {a} ∗ v2 ∈ {b} ∗。
在归纳开始时：在 i = 0 时，它产生 w 是 ε，在 i = 1 时，w 是 {ε, abS}。
到目前为止是这样吗？
so here a grammar R and a Langauge L, I want to prove that from R comes out L.
您可能想要做的是表明某些语法 R 的语言 L(R) 与另一种指定的其他语言 L 相同（在您的情况下，使用正则表达式的集合生成器表示法）。
so I thought I would prove that L(G) ⊆ L and L(G) ⊇ L are right.
鉴于上述假设，您认为这是进行证明的正确方法是正确的。
for L (G) ⊆ L: I show by induction on the number i of derivative steps that after every derivative step u → w through which w results from u according to the rules of R, w = v1v2 or w = v1v2w with | v2 | = | v1 | and v1 ∈ {a} ∗ and v2 ∈ {b} ∗. and in the induction start: at i = 0 it produces that w is ε and at i = 1 w is {ε, abS}.
这对我来说很难理解。这并不是说这是错误的。让我用自己的话写下来，也许你或其他人可以判断我们是否在说同样的话。
我们要证明L(R)是L的一个子集，即由文法R生成的任何字符串都包含在语言L中。我们可以通过对步骤数的数学归纳来证明这一点语法生成的字符串的推导。我们从一个推导步骤的基本情况开始：S -> e 通过选择 n = 0 产生空词，它是语言 L 中的一个字符串。现在我们已经建立了基本情况，我们可以陈述归纳假设：假设对于在直到并包括 k 的多个步骤中从文法导出的所有字符串，这些字符串也在 L 中。现在我们必须证明归纳步骤：从文法中在 k+1 个步骤中导出的任何字符串也在 L 中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 步中的语法派生的所有字符串也在该语言中。
为了证明语言中的所有字符串都可以在文法中导出，考虑以下构造：要在文法中导出字符串 (ab)^n，应用产生式 S -> abS 多次等于到 n，并且产生式 S -> e 恰好一次。第一步给出一个中间形式 (ab)^nS，第二步给出一个封闭形式的字符串 (ab)^n.
所以这里有语法R和语言L，我想证明从R出来L。
R={S→abS|ε} , L={(ab)n|n≥0}
所以我想我会证明 L(G) ⊆ L 和 L(G) ⊇ L 是正确的。
对于 L (G) ⊆ L：我通过对导数步骤 i 的归纳表明，在每个导数步骤 u → w 之后，w 根据 R 的规则从 u 中得出，w = v1v2 或 w = v1v2w 与 | v2 | = | v1 | v1 ∈ {a} ∗ v2 ∈ {b} ∗。 在归纳开始时：在 i = 0 时，它产生 w 是 ε，在 i = 1 时，w 是 {ε, abS}。
到目前为止是这样吗？
so here a grammar R and a Langauge L, I want to prove that from R comes out L.
您可能想要做的是表明某些语法 R 的语言 L(R) 与另一种指定的其他语言 L 相同（在您的情况下，使用正则表达式的集合生成器表示法）。
so I thought I would prove that L(G) ⊆ L and L(G) ⊇ L are right.
鉴于上述假设，您认为这是进行证明的正确方法是正确的。
for L (G) ⊆ L: I show by induction on the number i of derivative steps that after every derivative step u → w through which w results from u according to the rules of R, w = v1v2 or w = v1v2w with | v2 | = | v1 | and v1 ∈ {a} ∗ and v2 ∈ {b} ∗. and in the induction start: at i = 0 it produces that w is ε and at i = 1 w is {ε, abS}.
这对我来说很难理解。这并不是说这是错误的。让我用自己的话写下来，也许你或其他人可以判断我们是否在说同样的话。
我们要证明L(R)是L的一个子集，即由文法R生成的任何字符串都包含在语言L中。我们可以通过对步骤数的数学归纳来证明这一点语法生成的字符串的推导。我们从一个推导步骤的基本情况开始：S -> e 通过选择 n = 0 产生空词，它是语言 L 中的一个字符串。现在我们已经建立了基本情况，我们可以陈述归纳假设：假设对于在直到并包括 k 的多个步骤中从文法导出的所有字符串，这些字符串也在 L 中。现在我们必须证明归纳步骤：从文法中在 k+1 个步骤中导出的任何字符串也在 L 中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 步中的语法派生的所有字符串也在该语言中。
为了证明语言中的所有字符串都可以在文法中导出，考虑以下构造：要在文法中导出字符串 (ab)^n，应用产生式 S -> abS 多次等于到 n，并且产生式 S -> e 恰好一次。第一步给出一个中间形式 (ab)^nS，第二步给出一个封闭形式的字符串 (ab)^n.