私は自分のテストでこの質問を間違え、誰かがそれを説明できるかどうか疑問に思っていました。そして、結論に達するためにとられたステップを示しました。どんな助けでもいただければ幸いです。
L_neq = {0 ^ i1 ^j|のPL証明で i <j} m状態のDFAが与えられた場合、誰かが文字列0 ^（m / 2）1 ^（m / 2 + 1）を選択します。次に、y = 0を選択し、ポンピングすることで、L_neqの外側にある文字列0 ^（m / 2 + 1）1 ^（m / 2 + 1）に到達できることを示します。この証明は正しいですか？なぜまたはなぜそうではないのですか？
さらに、この証明が間違っている場合は、正しい証明を書き留めてください。
ありがとう
ポンピング補題を使用する場合、ポンピングする文字列を選択することはできますが（wと呼びましょう）、wを3つの部分xyzに分割する方法を選択することはできません。代わりに、あなたがする必要があるのは、wをxyzに分割できる方法について、xyiz∉Lneqとなるようなxyizとなるようなiの選択があることを示すことです。したがって、y = 0の場合、文字列をL neqから取り出すことができるというのは正しいですが、y = 0を保証することはできません。代わりに、|xy|のようなyを選択する場合はそれを示す必要があります。≤mおよび|y| > 0の場合、言語から文字列を削除できます。
ヒントとして、文字列0 m1mを試してください。さて、| xy |以来、yの任意の選択に対して ≤mの場合、自然数j>0に対してyの形式は0jでなければならないことがわかります。次に、引数を使用して、xyizがLneqに存在しないことを示すことができます。
ポンピング補題とこれらの証明がどのように機能するかに関する別のリソースについては、計算理論コースで今四半期初めに使用したこれらの講義スライドを自由にチェックしてください。彼らはいくつかの反復補題の例をウォークスルーし、（重要なことに）これらの証明について考えるための敵対的なモデルを披露します。
お役に立てれば！