具有泵引理的语言的规律性
Regularity of a language With pumping Lemma
将字符串解释为 Z ≥0 中的二进制数字（可能带有前导零，此处没有模运算）。以下超过 {0, 1} 的语言是常规的
{xyz : |x| = |y| = |z| and x + y = z}?
我认为要证明这种语言的非正则性，我应该应用 Pumping Lemma 并证明不存在满足 Pumping Lemma 的所有三个条件的可能设置。
考虑长度为 3p + 3 的字符串 (0^p)1(0^p)1(0^p-1)10。这是语言中的一个字符串，因为选择 |x| = |y| = |z|意味着 x = (0^p)1, y = (0^p)1 and z = (0^p-1)10, and 1 + 1 = 10. 现在，泵引理说这可以写成首先是：
- |rs| <= p
- |s| > 0
- r(s^k)t 是所有自然数 k
的语言
请注意，在我们的例子中，s 必须完全由组件 x 的前导 0 组成。假设我们选择k = 0。有几种情况需要考虑：
- |转|不能被 3 整除。在这种情况下，字符串不可能是我们的语言，因为条件 |x| = |y| = |z|无法满足。
- 如果 |rt|可以被 3 整除，考虑我们的新 x、y 和 z：我们删除了前导 0 的一些数字 3m。这意味着 |x| = |y| = |z| = p + 1 - 米。原来位于旧 x 末尾的 1 将在新字符串中左移 (m - 1) 个位置； y 末尾的 1 最初将在新字符串中左移 (m - 2) 个位置； z 末尾的 1 将保留在 z 中的倒数第二个位置。
- 如果m = 1，则y将不再包含任何1，所以无法满足x + y + z
- 如果m > 1，则x代表大于或等于10的数，y代表正数。但是，大于等于10的数与正数（非零）的和不能等于10。所以，这里也不能满足x + y + z。
因此，m = |s| 别无选择这样选择 k = 0 就可以得到语言中的 r(s^k)t。这是一个矛盾，因此我们隐含的语言是正则的假设一定是错误的。
将字符串解释为 Z ≥0 中的二进制数字（可能带有前导零，此处没有模运算）。以下超过 {0, 1} 的语言是常规的
{xyz : |x| = |y| = |z| and x + y = z}?
我认为要证明这种语言的非正则性，我应该应用 Pumping Lemma 并证明不存在满足 Pumping Lemma 的所有三个条件的可能设置。
考虑长度为 3p + 3 的字符串 (0^p)1(0^p)1(0^p-1)10。这是语言中的一个字符串，因为选择 |x| = |y| = |z|意味着 x = (0^p)1, y = (0^p)1 and z = (0^p-1)10, and 1 + 1 = 10. 现在，泵引理说这可以写成首先是：
- |rs| <= p
- |s| > 0
- r(s^k)t 是所有自然数 k 的语言
请注意，在我们的例子中，s 必须完全由组件 x 的前导 0 组成。假设我们选择k = 0。有几种情况需要考虑：
- |转|不能被 3 整除。在这种情况下，字符串不可能是我们的语言，因为条件 |x| = |y| = |z|无法满足。
- 如果 |rt|可以被 3 整除，考虑我们的新 x、y 和 z：我们删除了前导 0 的一些数字 3m。这意味着 |x| = |y| = |z| = p + 1 - 米。原来位于旧 x 末尾的 1 将在新字符串中左移 (m - 1) 个位置； y 末尾的 1 最初将在新字符串中左移 (m - 2) 个位置； z 末尾的 1 将保留在 z 中的倒数第二个位置。
- 如果m = 1，则y将不再包含任何1，所以无法满足x + y + z
- 如果m > 1，则x代表大于或等于10的数，y代表正数。但是，大于等于10的数与正数（非零）的和不能等于10。所以，这里也不能满足x + y + z。
因此，m = |s| 别无选择这样选择 k = 0 就可以得到语言中的 r(s^k)t。这是一个矛盾，因此我们隐含的语言是正则的假设一定是错误的。