regex - 查找泵引理条件中的错误

Question

在我的考试中，我应该写出所有的抽引引理条件。这正是我所做的：

一位朋友告诉我有一些错误，但我找不到它们......有人可以帮忙吗？有什么错误&为什么？

Answer 1

如果我没记错的话，条件需要如下：

• | x y | ≤ p
• | 是| ≥1 _
• xy ⁱ z ∈ L , i ≥ 0

所以y不能为空，并且y可以重复零次或多次。

Answer 2

你几乎是对的，但抽水引理要求 |xy| ≤ p，不是 |xz| ≤ p。这个想法是将字符串分成一些初始化 (x)、稳态 (y) 和尾部 (z)，并且初始化加上稳态逻辑有一定的长度。