求助构造满足子串及字符计数奇偶要求的有限自动机

思路：用乘积自动机组合两个子DFA #

因为你要满足的四个条件都是正则语言的要求，它们的交集也是正则语言，所以可以把两个独立的DFA组合成一个乘积DFA：一个负责检测字符串是否包含子串"1002"，另一个负责跟踪1、2的出现次数是否为奇数，0的出现次数是否为偶数。

第一个子DFA：检测子串"1002" #

这个DFA的状态对应匹配"1002"的前缀进度：

• S0：还没匹配到任何前缀
• S1：刚匹配到"1"
• S2：刚匹配到"10"
• S3：刚匹配到"100"
• S4：已经匹配完完整的"1002"（进入这个状态后，不管再输入什么字符，都保持在S4）

它的转移规则很直观：

第二个子DFA：跟踪字符计数奇偶性 #

用三元组(a, b, c)表示状态，每个元素取0或1：

• a=0：1出现偶数次；a=1：1出现奇数次
• b=0：2出现偶数次；b=1：2出现奇数次
• c=0：0出现偶数次；c=1：0出现奇数次

输入字符时，只翻转对应字符的奇偶位：

组合成最终的乘积DFA #

把两个DFA的状态合并，最终的状态格式是(Si, a,b,c)，其中Si是第一个DFA的状态，(a,b,c)是第二个DFA的状态。

初始状态 #

初始时没有输入任何字符，所以状态是(S0, 0,0,0)：没匹配到前缀，所有字符出现次数都是0（偶数）。

转移规则 #

结合两个子DFA的转移逻辑，逐个状态组说明：

当处于(S0, a,b,c)时

• 输入0：回到S0，同时翻转0的奇偶性 → (S0, a, b, 1-c)
• 输入1：转到匹配"1"的状态S1，翻转1的奇偶性 → (S1, 1-a, b, c)
• 输入2：回到S0，翻转2的奇偶性 → (S0, a, 1-b, c)

当处于(S1, a,b,c)时

• 输入0：转到匹配"10"的状态S2，翻转0的奇偶性 → (S2, a, b, 1-c)
• 输入1：保持在S1（重新匹配"1"），翻转1的奇偶性 → (S1, 1-a, b, c)
• 输入2：回到S0，翻转2的奇偶性 → (S0, a, 1-b, c)

当处于(S2, a,b,c)时

• 输入0：转到匹配"100"的状态S3，翻转0的奇偶性 → (S3, a, b, 1-c)
• 输入1：转到S1（重新匹配"1"），翻转1的奇偶性 → (S1, 1-a, b, c)
• 输入2：回到S0，翻转2的奇偶性 → (S0, a, 1-b, c)

当处于(S3, a,b,c)时

• 输入0：回到S0（匹配"100"后输入0，无法延续前缀），翻转0的奇偶性 → (S0, a, b, 1-c)
• 输入1：转到S1（重新匹配"1"），翻转1的奇偶性 → (S1, 1-a, b, c)
• 输入2：转到匹配完成的状态S4，翻转2的奇偶性 → (S4, a, 1-b, c)

当处于(S4, a,b,c)时

已经匹配到"1002"，之后不管输入什么都保持在S4，同时更新对应字符的奇偶性：

• 输入0 → (S4, a, b, 1-c)
• 输入1 → (S4, 1-a, b, c)
• 输入2 → (S4, a, 1-b, c)

接受状态 #

只有同时满足以下条件的状态才是接受状态：

1. 已经匹配到子串"1002" → Si = S4
2. 1出现奇数次 → a=1
3. 2出现奇数次 → b=1
4. 0出现偶数次 → c=0

也就是唯一的接受状态：(S4, 1,1,0)

举个例子验证 #

比如输入字符串"1002"：

1. 初始状态(S0,0,0,0) → 输入1 → 状态(S1,1,0,0)
2. 输入0 → 状态(S2,1,0,1)
3. 输入0 → 状态(S3,1,0,0)
4. 输入2 → 状态(S4,1,1,0)，到达接受状态，符合所有条件。

再比如输入"10020"：
到达(S4,1,1,0)后输入0 → 状态(S4,1,1,1)，此时0的次数是奇数，不再是接受状态，符合要求。

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