是否存在两状态TG可接受不在EVEN-EVEN语言中的{a,b}*字符串？

结论：不存在这样的两状态转移图（TG）

前提定义 #

• 目标可接受语言L是EVEN-EVEN的补集，即字母表{a,b}生成的所有字符串中，满足「a的个数为奇数 或 b的个数为奇数」的字符串集合。
• 转移图（TG）的表达能力与非确定有限自动机（NFA）等价，可识别的语言范围与确定性有限自动机（DFA）完全一致，均为正则语言。

反证法推导 #

假设存在符合要求的两状态TG，我们将其等价转换为最多2状态的NFA，设两个状态为起始态S₀、另一状态S₁：

1. 空串ε的a、b个数均为偶数，属于EVEN-EVEN，因此L不能接受ε，说明起始态S₀不能是终态，唯一可选的终态只有S₁。
2. 单字符字符串a、b均满足L的要求，因此必然存在从S₀读入a/b后到达S₁的转移路径。
3. 字符串aa、bb的a、b个数均为偶数，属于EVEN-EVEN，不能被L接受：因此读入第二个a/b时，从S₁出发的转移不能停在S₁，只能回到S₀。
4. 此时验证字符串ab：ab的a、b个数均为奇数，属于L，应当被接受。但按照上述转移路径，S₀读a到S₁，S₁读b回到S₀，最终停在非终态S₀，无法被接受，出现矛盾。

如果尝试调整转移规则，比如允许S₁读入字符后同时转移到S₀和S₁，则会导致aa、bb存在到达S₁的路径，被误判为属于L，同样不符合要求。

内容的提问来源于stack exchange，提问作者Ibrahim