computation-theory - 带有抽引理的语言的规律性

Question

将字符串解释为Z ≥0二进制中的数字（可能带有前导零，这里没有模运算）。以下语言{0, 1}是否正常 {xyz : |x| = |y| = |z| and x + y = z}？

我认为为了证明这种语言的非规律性，我应该应用 Pumping Lemma 并证明不存在满足所有三个 Pumping lemma 条件的可能设置。

Answer 1

考虑长度为 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。有几种情况需要考虑：

• |rt| 不能被 3 整除。在这种情况下，字符串不可能是我们的语言，因为条件 |x| = |y| = |z| 不能满足。
• 如果 |rt| 可以被 3 整除，考虑我们的新 x、y 和 z：我们删除了一些 3m 的前导 0。这意味着 |x| = |y| = |z| = p + 1 - 米。最初位于旧 x 末尾的 1 将在新字符串中左移 (m - 1) 个位置；y 末尾的 1 最初将在新字符串中左移 (m - 2) 个位置；z 末尾的 1 将保留在 z 中的倒数第二个位置。
  1. 如果 m = 1，则 y 将不再包含任何 1，因此无法满足 x + y + z
  2. 如果 m > 1，则 x 将表示大于或等于 10 的数字，y 将表示正数。但是，大于或等于 10 的数与正（非零）数之和不能等于 10。因此，这里也不能满足 x + y + z。

因此，没有选择 m = |s| 这样选择 k = 0 就可以得到语言中的 r(s^k)t。这是一个矛盾，因此我们隐含的语言是规则的假设一定是错误的。