我们如何使用泵引理证明这种语言是不规则的？
how do we prove that this language is irregular using the pumping lemma?
在解决问题时，我遇到了一个棘手的问题，要求我使用泵引理证明某种语言是不规则的。该问题如下：
使用泵引理证明语言 L 是不规则的，其中 L 是字母表 {0,1,$} 上的语言。
L = { XW$WY | X,Y ∈ {0,1}*, W ∈ {0,1}+ }
我的方法是选择一个字符串 S = 0p$0p 其中 X 和 Y 等于 Э，并且P 是泵送长度。
现在，让我们将字符串分成 3 个部分，我们称它们为 Y1、Y2、Y3。
为了满足抽取引理的条件，这 3 个部分的串联必须具有 > P 的长度，并且 |Y2| > 0，并且 |Y1Y2| <= P.
所以我们的 Y1 和 Y2 将仅由 0 组成，而 Y3 将是 $0p。所以，我们的字符串看起来像这样： 0i0j$0p 其中 i+j < = P. 显然抽取 Y2(0j) 会改变第一个 W 的长度，因此新字符串 Y1Y2iY3 不属于 L。但令我困惑的是，我们总是可以更改 X 以使第一个 W 等于第二个。所以，无论 i 是什么，我们总是可以假设长度的差异实际上是因为 X。我是不是漏掉了什么？
是的，由于您解释的原因，您选择的字符串是错误的：您无法确定 X 是什么。但是，我们可以强制选择 X。考虑 1 0^p $ 1 0^p。这只能是 X = 空和 Y = 空的语言中的字符串。泵 v 只能影响 $ 之前的前缀，并且总是会导致字符串不是该语言，矛盾。
在解决问题时，我遇到了一个棘手的问题，要求我使用泵引理证明某种语言是不规则的。该问题如下：
使用泵引理证明语言 L 是不规则的，其中 L 是字母表 {0,1,$} 上的语言。
L = { XW$WY | X,Y ∈ {0,1}*, W ∈ {0,1}+ }
我的方法是选择一个字符串 S = 0p$0p 其中 X 和 Y 等于 Э，并且P 是泵送长度。
现在，让我们将字符串分成 3 个部分，我们称它们为 Y1、Y2、Y3。
为了满足抽取引理的条件，这 3 个部分的串联必须具有 > P 的长度，并且 |Y2| > 0，并且 |Y1Y2| <= P.
所以我们的 Y1 和 Y2 将仅由 0 组成，而 Y3 将是 $0p。所以，我们的字符串看起来像这样： 0i0j$0p 其中 i+j < = P. 显然抽取 Y2(0j) 会改变第一个 W 的长度，因此新字符串 Y1Y2iY3 不属于 L。但令我困惑的是，我们总是可以更改 X 以使第一个 W 等于第二个。所以，无论 i 是什么，我们总是可以假设长度的差异实际上是因为 X。我是不是漏掉了什么？
是的，由于您解释的原因，您选择的字符串是错误的：您无法确定 X 是什么。但是，我们可以强制选择 X。考虑 1 0^p $ 1 0^p。这只能是 X = 空和 Y = 空的语言中的字符串。泵 v 只能影响 $ 之前的前缀，并且总是会导致字符串不是该语言，矛盾。