1
让语言L_n具有字符集Sigma = {a_1，...，a_n}。 L_n恰好包含那些包含一些奇数次字符的单词。等价地，如果L_n^i是每个包含奇数个a_i的字的语言，则L_n = L_n^1 union ... union L_n^n。证明具有k <2^n个状态的任何DFA不接受具有奇数个字符的字符串
我已经产生了接受L_n和2^n状态的DFA的NFA，
我现在需要证明这是接受此语言的最小DFA。我给出的提示假设有为k < 2^n种状态，它接受L_N的DFA，然后显示，有一些字符串U，V西格玛^ *，其中ü包含一个和奇数次数，v包含偶数次，并且DFA必须在相同状态下终止。
我一直在试图把2^n看作一个强有力的暗示，比如可能考虑所有长度为n的字符串，但是有n^n个这样的字符串。也许考虑所有长度为n的字符串，只使用字符a，b。由于有2^n个状态，因此必须将这样的一些两个字符串发送到相同的状态。在这个集合中被拒绝的字符串是那些偶数为a和b但我无法知道两个这样的实例是否处于相同的状态，或者如果他们这样做，那又怎么样。
也许考虑所有的字符串选择，其中a_1出现一次或0次，a_2出现一次或0次等等。有2^n个选择，因此其中的2个必须进入相同的状态。这里不存在的唯一字符串是空字符串。仍然我卡住了。