私の質問は、正規言語のポンピング補題を使用して、有限言語の最長文字列がその言語を認識する DFA の状態数よりも少なくなければならないことを証明することに関するものです。これについて代数的な議論を見つけたいと思っていましたが、その証明はピジョンホールの原理に頼らなければならないようです。p = 有限言語を認識する DFA 内の状態の数である場合、ピジョンホールの原則により、最長の文字列は p-1 に等しいサイズでなければなりません (つまり、すべてのピジョンホールにはピジョンが含まれている必要があります。文字列は有限であるため、複数の鳩がいる鳩の巣は存在しません)。
有限言語の最長文字列の長さが p-1 未満の場合、最長文字列が受け入れ状態に到達する保証はありません。長さが p-1 より大きい場合、文字列が完全に処理される前に計算が「終了」する必要があるため、DFA によって受け入れられません。
上記は、有限言語の最長の文字列の長さが状態の数以下でなければならないことを証明するための有効な引数ですか?