问：泵引理证明
Q: Pumping Lemma Proof
我最近有一个作业，我必须用抽取引理来决定语言是否是规则的。
L1 = {xy ∈ {a, b}∗ : |x| = |y|，要么 x 以 a 开头，y 以 b 结尾，要么 x 和 y 都不是所有 a 的字符串}。
L2 = {xy ∈ {a, b}∗ : |x| = |y|，x包含子字符串aa，y以a b}开头。
对于假设泵送长度为 n 的两种语言，我提供了字符串 s = (a^n)(b^n) 因为它满足“|x| = |y|，x 以 a 开头，y 以 a 结尾a b”条件和L2的“|x| = |y|，x包含子串aa，y以a b开头”条件。所以，s = x(y^i)z，我选择了 x = (a^n-1), y = a, z = b^n。对于任何偶数的 i，总字母数在 x(y^i)z 中是奇数，这样 s 不在 L1 和 L2 中，因为 |x|不能等于 |y|了。我只是想知道我是否做对了或者我错过了什么？
对于 L1，令 w = a^pbba^p。那么w在L1中是因为它可以分为长度相同的子串x = a^pb和y = ba^p，两者都不是只有a的串。通过常规语言的泵送引理，w = uvx 其中|uv| <= p, |v| > 0且uv^kx对于所有自然数k >= 0都在L1中。但是uv必须是从字符串开头的a的字符串；向上抽取将导致 x，即结果字符串的前半部分，仅由 a 组成（假设该字符串仍然是偶数长度的字符串；否则，该字符串无论如何都不能在 L1 中）；抽空将导致 y，即结果字符串的后半部分，仅由 a 组成。无论哪种方式，生成的字符串都不在该语言中。这意味着L1不能是正则的。
对于 L2，令 w = a^paba^p。 Pumping up 意味着生成的字符串将以 a 开头（或具有奇数长度），pumping down 也是如此。在前一种情况下，结果字符串的 y 将从 w 的前半部分开始。在后者中，结果字符串的 y 将从 w 的后半部分开始。无论如何，我们得到的字符串不是该语言，因此 L2 也不是正则的。
我最近有一个作业，我必须用抽取引理来决定语言是否是规则的。
L1 = {xy ∈ {a, b}∗ : |x| = |y|，要么 x 以 a 开头，y 以 b 结尾，要么 x 和 y 都不是所有 a 的字符串}。
L2 = {xy ∈ {a, b}∗ : |x| = |y|，x包含子字符串aa，y以a b}开头。
对于假设泵送长度为 n 的两种语言，我提供了字符串 s = (a^n)(b^n) 因为它满足“|x| = |y|，x 以 a 开头，y 以 a 结尾a b”条件和L2的“|x| = |y|，x包含子串aa，y以a b开头”条件。所以，s = x(y^i)z，我选择了 x = (a^n-1), y = a, z = b^n。对于任何偶数的 i，总字母数在 x(y^i)z 中是奇数，这样 s 不在 L1 和 L2 中，因为 |x|不能等于 |y|了。我只是想知道我是否做对了或者我错过了什么？
对于 L1，令 w = a^pbba^p。那么w在L1中是因为它可以分为长度相同的子串x = a^pb和y = ba^p，两者都不是只有a的串。通过常规语言的泵送引理，w = uvx 其中|uv| <= p, |v| > 0且uv^kx对于所有自然数k >= 0都在L1中。但是uv必须是从字符串开头的a的字符串；向上抽取将导致 x，即结果字符串的前半部分，仅由 a 组成（假设该字符串仍然是偶数长度的字符串；否则，该字符串无论如何都不能在 L1 中）；抽空将导致 y，即结果字符串的后半部分，仅由 a 组成。无论哪种方式，生成的字符串都不在该语言中。这意味着L1不能是正则的。
对于 L2，令 w = a^paba^p。 Pumping up 意味着生成的字符串将以 a 开头（或具有奇数长度），pumping down 也是如此。在前一种情况下，结果字符串的 y 将从 w 的前半部分开始。在后者中，结果字符串的 y 将从 w 的后半部分开始。无论如何，我们得到的字符串不是该语言，因此 L2 也不是正则的。