求字母表{a,b}下含相等偶数个a和b的DFA（TOC新手求指引）

你要识别的语言不是正则语言，而DFA只能识别正则语言，因此不存在能满足需求的确定有限自动机。

用正则语言的泵引理可以简单证明：
假设这个语言是正则的，那么存在一个固定长度p（泵长度），只要字符串长度超过p，就能拆成三段x、y、z，其中y至少有一个字符，并且不管把y重复多少次（0次、1次、2次...），得到的新字符串都还属于这个语言。
我们取字符串s = (aabb)^p，这个字符串里a和b各有2p个，显然属于你的语言，而且长度是4p，肯定超过p。
现在把s拆成x、y、z，y是前p个字符里的某一段：

• 如果y是几个连续的a，那把y重复一次，新字符串里a的数量就变成2p + |y|，b还是2p，a和b数量不等，不属于你的语言，矛盾。
• 如果y包含a和b，比如y是"ab"，重复y后，a和b的数量各加了1，变成2p+1，数量相等但都是奇数，也不属于你的语言，矛盾。
  这说明假设不成立，你的语言不是正则语言，DFA无法识别它。

如果一定要构造自动机识别这个语言，可以用带栈的下推自动机，核心是用栈跟踪a和b的数量差，同时记录a的数量奇偶性：

• 初始状态：栈底放一个特殊符号#，当前状态为接受状态（对应空串）
• 关键转移规则（简化版）：
  • 当栈为空（a和b数量相等）且a数量是偶数时：
    • 输入a：把a压入栈，切换到“a比b多1，a数量奇”的状态
    • 输入b：把b压入栈，切换到“b比a多1，a数量偶”的状态
  • 当栈顶是a（a比b多）时：
    • 输入a：继续压a，更新状态的奇偶性和差值
    • 输入b：弹出栈顶的a，若栈变空，检查a数量奇偶性——如果是偶数就回到接受状态，否则进入“数量相等但都是奇数”的状态
  • 当栈顶是b（b比a多）时：
    • 输入b：继续压b，更新状态的奇偶性和差值
    • 输入a：弹出栈顶的b，若栈变空，检查a数量奇偶性——如果是偶数就回到接受状态，否则进入“数量相等但都是奇数”的状态
• 只有当栈为空且a数量是偶数时，才是接受状态。

你提到的“识别偶数个a和偶数个b的DFA”是存在的，因为这个语言只需要跟踪a和b的奇偶性，用4个状态就能实现；但你的需求额外要求a和b数量相等，这需要跟踪无限种可能的数量差，DFA的有限状态做不到这一点。

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