これは、言語が正規ではないことを実証するための正規言語です。Lが正規言語の場合、| z |> = NのLの各zについて、zを3つに分割できる定数Nがあります。次のようなサブ文字列（uvw = z）：
1)|uv|<=N;
2)|v|>=1;
3)For each k>=0, uv^kw in L.
Nは、Lを受け入れるDFAの状態の最小数以下である必要があります。したがって、ポンピング補題を適用するには、Lを受け入れるDFAが最小になる状態の数を知る必要があります。では、最小のDFAを構築せずに、最小の状態数を知ることは可能ですか？
N は、L を受け入れる DFA の状態の最小数以下でなければなりません
N は、L を受け入れる最小 DFA の状態数よりも少なくすることはできません。それ以外の場合、DFA は L を受け入れることができません (可能であれば、L を受け入れる最小の DFA よりも小さい L を受け入れる DFA を持つことになり、矛盾します)。N は、L を受け入れる最小限の DFA の状態の数に等しいと安全に想定できます (そのような DFA は一意です)。
したがって、ポンピング補題を適用するには、L を受け入れる最小 DFA を持つ状態がいくつあるかを知る必要があります。
これは厳密には正しくありません。ほとんどのポンピング補題の証明では、N が実際に何であるかは問題ではありません。ターゲット文字列が他のプロパティを満たしていることを確認するだけです。DFA が与えられた場合、最小限の DFA が持つ状態の数を決定することができます。ただし、DFA がある場合は、L が正則であることは既にわかっているため、ポンピング補題を気にする必要はありません。実際、L を受け入れる N 個の状態を持つ最小限の DFA が存在するように N を決定することは、問題の言語が実際に規則的であることの有効な証拠を構成します。
では、最小限の DFA を構築せずに状態の最小数を知ることは可能でしょうか?
言語の記述を分析し、Myhill-Nerode の定理を使用することで、最小 DFA を実際に構築しなくても、言語が規則的であることの証明を構築し、最小 DFA の状態数を見つけることができます (ただし、いったん完了したら、 Myhill-Nerode を使用したそのような証明では、最小限の DFA の構築は自明な演習です)。ポンピング補題の代わりに Myhill-Nerode を使用して、言語が規則的ではないことを証明することもできます。これは、言語の最小限の DFA が無限に多くの状態 (矛盾) を持つ必要があることを示すことによって行われます。
これらの観察があなたの質問に答えているかどうか教えてください。追加の説明を提供させていただきます。