言語 L_n に文字セット Sigma = {a_1, ..., a_n} があるとします。L_n には、ある文字を奇数回含む単語が正確に含まれています。同様に、L_n^i が、各単語に奇数個の a_i が含まれる言語である場合、L_n = L_n^1 union ...union L_n^n となります。
L_n を受け入れる NFA と 2^n 状態の DFA も作成しました。
これがこの言語を受け入れる最小の DFA であることを証明する必要があります。L_n を受け入れる k < 2^n 状態の DFA があると仮定するためのヒントが与えられ、次にSigma^* にいくつかの文字列u、vがあることを示します。偶数回であり、DFA は両方で同じ状態で終了する必要があります。
長さ n のすべての文字列を考えてみてください。おそらく、文字a,bのみを使用して長さ n のすべての文字列を検討してください。k < 2^n の状態があるため、このような 2 つの文字列を同じ状態に送信する必要があります。このセットで拒否された文字列は、a と b の数が偶数の文字列ですが、これらの2 つのインスタンスが同じ状態になるかどうか、または同じ状態になった場合、それがどのように問題になるかを知る方法はありません。
おそらく、a_1 が 1 回または 0 回発生し、a_2 が 1 回または 0 回発生する文字列のすべての選択肢を検討してください。これらには 2^n の選択肢があるため、これらのいくつかの 2 つが同じ状態になる必要があります。ここの言語にない唯一の文字列は空の文字列です。それでも私は立ち往生しています。