泵引理辅助
Pumping Lemma Assistance
我最近有一个作业，要求我使用抽水引理来证明一种语言是不规则的，不幸的是我得到了错误的答案。
证明语言是非常规的如下：
L = {ai bj ck: i = j 或 j = k}
我得到的泵引理的定义如下：
- 对手选择 m
- 我想选择 w 来反驳泵引理。使用 m 来选择一个字符串 w ∈ L where |w| ≥米
- 对手选择受约束的 w 分解。
- 我尝试选择一个 i 以便抽取字符串 wi ∉ L。如果找到，L 不是正则的
事实证明，这个主题对我来说非常难以理解，因此我觉得自己像个彻头彻尾的傻瓜，所以如果能详细解释我如何正确应用抽水引理，我们将不胜感激。
直觉上，抽取引理表示在常规语言 L 中足够长的单词（长度仅取决于语言 L）必须包含一个部分（长度 > 0），该部分可以根据需要重复多次。重复该部分（'pumping' 原始单词）任意次数会产生一些更长的单词，这些单词也在语言 L 中。
单词的最小长度为上述定义第一步中的m；该部分重复的次数是上面定义的第4步中的i。
泵引理通常用来表示一个语言L不是正则的。这是一个矛盾的证明：假设 L 是规则的，因此规则语言的抽取引理对 L 是正确的。然后选择一个在 L 中足够长*的词 w 并表明无论它如何分解*一些抽取单词不在语言中。这与泵引理相矛盾——我们知道它是正确的。因此，我们假设语言是规则的是错误的，因此语言是不规则的。不能选择标有 * 的部分以使事情变得简单 - 这就是为什么在步骤 1 和 3 中 'opponent' select 是它们。
单词w重写为w = x y z，其中|是 | > 0 和 |x y| <=米。 x 和 z 的长度都可以是 0.
通常的方法是选择 xy 作为由相同字母组成的字符串，这样具有更多相同字母（在抽取之后）会导致单词不在 L 中。
在post语言L中没有对i或k指定限制，所以假设i = 0是允许的，一个合适的词可能是b^m c^m（即m bs 后跟 m cs)。现在无论对手可能 select 进行何种分解，y 总是由一些 b 组成。重复这些 bs 会导致 bs 多于 cs 而没有 as 的单词，因此 i != j 和 j!= k 并且该单词不在语言中。
我最近有一个作业，要求我使用抽水引理来证明一种语言是不规则的，不幸的是我得到了错误的答案。
证明语言是非常规的如下： L = {ai bj ck: i = j 或 j = k}
我得到的泵引理的定义如下：
- 对手选择 m
- 我想选择 w 来反驳泵引理。使用 m 来选择一个字符串 w ∈ L where |w| ≥米
- 对手选择受约束的 w 分解。
- 我尝试选择一个 i 以便抽取字符串 wi ∉ L。如果找到，L 不是正则的
事实证明，这个主题对我来说非常难以理解，因此我觉得自己像个彻头彻尾的傻瓜，所以如果能详细解释我如何正确应用抽水引理，我们将不胜感激。
直觉上，抽取引理表示在常规语言 L 中足够长的单词（长度仅取决于语言 L）必须包含一个部分（长度 > 0），该部分可以根据需要重复多次。重复该部分（'pumping' 原始单词）任意次数会产生一些更长的单词，这些单词也在语言 L 中。
单词的最小长度为上述定义第一步中的m；该部分重复的次数是上面定义的第4步中的i。
泵引理通常用来表示一个语言L不是正则的。这是一个矛盾的证明：假设 L 是规则的，因此规则语言的抽取引理对 L 是正确的。然后选择一个在 L 中足够长*的词 w 并表明无论它如何分解*一些抽取单词不在语言中。这与泵引理相矛盾——我们知道它是正确的。因此，我们假设语言是规则的是错误的，因此语言是不规则的。不能选择标有 * 的部分以使事情变得简单 - 这就是为什么在步骤 1 和 3 中 'opponent' select 是它们。
单词w重写为w = x y z，其中|是 | > 0 和 |x y| <=米。 x 和 z 的长度都可以是 0.
通常的方法是选择 xy 作为由相同字母组成的字符串，这样具有更多相同字母（在抽取之后）会导致单词不在 L 中。
在post语言L中没有对i或k指定限制，所以假设i = 0是允许的，一个合适的词可能是b^m c^m（即m bs 后跟 m cs)。现在无论对手可能 select 进行何种分解，y 总是由一些 b 组成。重复这些 bs 会导致 bs 多于 cs 而没有 as 的单词，因此 i != j 和 j!= k 并且该单词不在语言中。