regex - 補題条件のポンピングエラーの検出

Question

私の試験では、すべての反復補題条件を書くことになっていた。それはまさに私がしたことです：

友人からエラーがあると言われましたが、見つかりません...誰か助けてもらえますか？エラーとその理由は何ですか？

Answer 1

私が正しく覚えている場合、条件は次のようにする必要があります。

• | x y | ≤p _
• | y | ≥1 _
• xy ^iz∈L、i≥0 _ _ _ _ _

したがって、 yは空であってはならず、yは0回以上繰り返すことができます。

Answer 2

あなたはほぼ正しいですが、ポンピングの補題には|xy|が必要です。≤p、|xz|ではない ≤p。文字列は初期化（x）、定常状態（y）、およびテール（z）に分割され、初期化と定常状態のロジックはある程度の長さであるという考え方です。