我最近有一个任务，我必须决定这些语言是否是常规的，或者不是带有引理。
L1 = {xy ∈ {a, b}∗ : |x| = |y|，要么 x 以 a 开头，y 以 ab 结尾，要么 x 和 y 都不是所有 a 的字符串}。
L2 = {xy ∈ {a, b}∗ : |x| = |y|，x 包含子字符串 aa，y 以 ab} 开头。
对于假设泵送长度为 n 的两种语言，我提供了字符串 s = (a^n)(b^n)，因为它满足 L1 的“|x| = |y|，x 以 a 开头，y 以 b 结尾”条件和“|x| = |y|, x 包含子串 aa 和 y 以 a b 开始” L2 的条件。所以，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 where |uv| <= p, |v| > 0 并且 uv^kx 对于所有自然数 k >= 0 都在 L1 中。但是，uv 必须是从字符串开头开始的 a 字符串；向上抽气会导致结果字符串的前半部分 x 仅由 a 组成（假设字符串仍然是偶数长度的字符串；否则，字符串无论如何都不能在 L1 中）；抽空将导致 y，即结果字符串的后半部分，仅包含 a。无论哪种方式，生成的字符串都不是该语言。这意味着 L1 不可能是正则的。
对于 L2，令 w = a^paba^p。向上抽气意味着生成的弦将以 a（或奇数长度）开头，向下抽气也是如此。在前一种情况下，结果字符串的 y 将以 w 前半部分的 a 开头；在后者中，结果字符串的 y 将从 w 的后半部分的 a 开始。在任何情况下，我们都会得到一个不是该语言的字符串，因此 L2 也不是正则的。