如何设计FSM(REGEX)识别包含奇数次重叠00模式的01序列？

状态定义 #

我们定义4种状态，每个状态同时跟踪两个核心信息：当前已出现的00模式累计次数的奇偶性、当前输入的最后一位是否为0：

• S0：初始状态，累计00出现次数为偶数，最后一位输入不是0（或无输入）
• S1：累计00出现次数为偶数，最后一位输入是0
• S2：累计00出现次数为奇数，最后一位输入不是0
• S3：累计00出现次数为奇数，最后一位输入是0

其中S2、S3为接受状态，只要序列处理完成后处于这两个状态，就表示符合要求。

状态转换表 #

对应正则表达式 #

匹配所有符合要求的01序列的正则表达式如下，适配00模式重叠计数的规则：
^1*(?:01*01*)*01*0(?:1*(?:01*01*)*01*0)*1*$

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