构造满足双条件的NFA：仅用6个状态接受指定正则语言

利用NFA的非确定性特性，通过ε转移同时运行两个独立的子自动机分别对应两个判定条件，任意子自动机到达接受态则整体接受，刚好可以控制在6个状态，完全满足要求。

状态定义 #

• S：初始状态
• A₀：子自动机1（校验a的个数奇偶）的状态，代表当前a的计数为偶数（接受态）
• A₁：子自动机1的状态，代表当前a的计数为奇数
• B₀：子自动机2（校验b的个数是否恰好为2）的状态，代表当前b的计数为0
• B₁：子自动机2的状态，代表当前b的计数为1
• B₂：子自动机2的状态，代表当前b的计数为2（接受态）

转移规则 #

1. 初始转移：S通过ε转移同时进入A₀和B₀
2. 子自动机1（A组）转移规则：
   • A₀接收a → A₁，接收b → A₀
   • A₁接收a → A₀，接收b → A₁
3. 子自动机2（B组）转移规则：
   • B₀接收a → B₀，接收b → B₁
   • B₁接收a → B₁，接收b → B₂
   • B₂接收a → B₂，接收b → 无有效转移（该分支终止，不影响另一分支运行）

测试验证 #

你提到的所有测试用例都可以正常识别：

• baabaa：a的个数为4（偶数），子自动机1最终停在A₀，接受
• abbba：b的个数为3，子自动机2分支终止，a的个数为2（偶数），子自动机1停在A₀，接受
• abba：a的个数为2（偶数，A₀）、b的个数为2（B₂），两个分支都到达接受态，接受
• baaab：b的个数为2，子自动机2停在B₂，接受

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