L={ww^Ru|w,u∈{0,1}+}是正则语言吗？

该问题可以使用 pumping lemma for regular languages 进行证明。

假设 L 是正则语言，则存在正整数 p （pump length），使得对于所有的字符串 w ∈ L，如果 |w| ≥ p，那么 w 可以被分解成三个子字符串 xyz，满足以下条件：

1. |y| > 0
2. |xy| ≤ p
3. 对于任意正整数 i，字符串 xy^iz 仍然在 L 中。

现在我们考虑字符串 s = 0^p1^p0^p1^p ∈ L，因为它满足：|s| ≥ p，并且 s 可以被分解成 s = xyz，其中：

x = ε，y = 0^p，z = 1^p0^p1^p。

根据 pumping lemma，我们可以修改 y，使得 xy^2z 不在 L 中，因为从 y 中任意删除一些 0 不会影响 x 和 z 中的 0 和 1 的配对，而仍然保持 s 属于 L，但是加入一些 0 后就不是 ww^Ru 的形式了。因此，L 不是正则语言。

代码示例（使用 Python 实现）：

def is_wwru_regular_language(): p = 1 while True: s = '0' * p + '1' * p + '0' * p + '1' * p if not is_wwru_language(s, p): print("L is not a regular language.") break p += 1

def is_wwru_language(s, p): for i in range(p): if s[i] != s[-i-1]: return False return True

is_wwru_regular_language()