泵引理和常规语言

Question

我需要解决这个有关抽引理的练习：

我不知道如何解决，教授没有解释清楚。 预先感谢。

Answer 1

设 L 为语言 {a^kb^j | k >= j >= 0}。假设相反L 是正则的。令 p 为由泵浦引理给出的泵浦长度。选择 s 作为字符串 a^pb^p。因为 s 是 L 的成员，并且 s 的长度大于 p，所以泵送引理保证 s 可以分为三部分，s = xyz，其中对于任何 i >= 0，字符串 xy^iz 在 L 中。

因为|xy| <= p (by the conditions of the lemma) and the first p symbols of s are as（因为我们选择s的方式），x和y中的所有符号都必须是as。因此，对于某些 k > 0，y = a^k（根据引理的条件）。我们可以通过使用 i = 0 得到矛盾，因为 xy^0z 仍然有 恰好是 p bs，但小于 p as。这是一个矛盾，因为泵浦引理说 xy^0z 在 L 中，但是对于 xy^0z，a的数量小于b的数量。这与泵送引理相矛盾，从而表明 L 是正则的假设必定是错误的。