所以这里有一个语法R和一个Langauge L，我想证明从R出来L。
R={S→abS|ε} , L={(ab)n|n≥0}
所以我想我会证明 L(G) ⊆ L 和 L(G) ⊇ L 是对的。
对于 L (G) ⊆ L：我通过对导数步骤数 i 的归纳表明，在每个导数步骤 u → w 之后，根据 R 的规则，w = v1v2 或 w = v1v2w 通过 | v2 | = | v1 | 和 v1 ∈ {a} ∗ 和 v2 ∈ {b} ∗。并且在归纳开始中：在 i = 0 时，它产生 w 是 ε 并且在 i = 1 时 w 是 {ε,abS}。
到目前为止是对的吗？
所以这里有一个语法R和一个Langauge L，我想证明从R出来L。
可能您想要做的是表明某些语法 R 的语言 L(R) 与另一种指定的其他语言 L 相同（在您的情况下，使用正则表达式的集合构建器表示法）。
所以我想我会证明 L(G) ⊆ L 和 L(G) ⊇ L 是对的。
鉴于上述假设，您认为这是进行证明的正确方法是正确的。
对于 L (G) ⊆ L：我通过对导数步骤数 i 的归纳表明，在每个导数步骤 u → w 之后，根据 R 的规则，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 个步骤，这些字符串也在 L 中。现在我们必须证明归纳步骤：从文法 k+1 步骤中导出的任何字符串也在L. 令 w 是从 k+1 步中的文法导出的任何字符串。从文法来看，w 的推导必须是 S -> abS -> ababS -> ... -> abab...abS -> abab...abe = abab...ab。但是这种推导与从文法中以 k 步推导字符串相同，只是在应用 S -> e 之前多了一个 S -> abS 应用。通过归纳假设，我们知道在 k 步中导出的字符串 w' 对于某些 m 至少为零的形式为 (ab)^m，并且在推导中添加 S -> abS 的额外应用会添加 ab。因为 (ab)^m(ab) = (ab)^(m+1) 我们可以选择 n = m+1。因此，根据需要，从 k+1 步中的语法派生的所有字符串也都在该语言中。通过归纳假设，我们知道在 k 步中导出的字符串 w' 对于某些 m 至少为零的形式为 (ab)^m，并且在推导中添加 S -> abS 的额外应用会添加 ab。因为 (ab)^m(ab) = (ab)^(m+1) 我们可以选择 n = m+1。因此，根据需要，从 k+1 步中的语法派生的所有字符串也都在该语言中。通过归纳假设，我们知道在 k 步中导出的字符串 w' 对于某些 m 至少为零的形式为 (ab)^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。