如何构造可识别由奇数长度0、1连续段组成的字符串的DFA

需求确认 #

构造字母表为{0,1}的DFA，仅满足以下规则的字符串可被接受：
字符串由若干连续同字符段交替拼接而成，每一段连续相同字符的长度均为奇数。

状态定义 #

通过两个维度定义状态：最后一个出现的字符类型、当前连续段的长度奇偶性，共包含6个状态（死状态可在状态图中省略，未明确标注的转移默认进入死状态）：

• S：初始状态，未读入任何字符
• A：上一个读入字符为0，当前0连续段的长度为奇数（接受状态）
• B：上一个读入字符为0，当前0连续段的长度为偶数
• C：上一个读入字符为1，当前1连续段的长度为奇数（*****
• D：上一个读入字符为1，当前1连续段的长度为偶数
• Q：死状态，字符串已出现不符合规则的段，永远无法被接受
  其中A、C为接受状态。

状态转移规则 #

• 初始状态S：
  • 输入0 → 转移到A
  • 输入1 → 转移到C
• 状态A：
  • 输入0 → 转移到B（连续0长度加1，奇偶性翻转）
  • 输入1 → 转移到C（*切换为1段，长度为1属于奇数）
• 状态B：
  • 输入0 → 转移到A（*连续0长度加1，奇偶性翻转）
  • 输入1 → 转移到Q（*当前0段长度为偶数，切换字符后该段成为非法段，整体串失效）
• 状态C：
  • 输入1 → 转移到D（*连续1长度加1，奇偶性翻转）
  • 输入0 → 转移到A（*切换为0段，长度为1属于奇数）
• 状态D：
  • 输入1 → 转移到C（*连续1长度加1，奇偶性翻转）
  • 输入0 → 转移到Q（*当前1段长度为偶数，切换字符后该段成为非法段，整体串失效）
• 死状态Q：任意输入均保留在Q

效果验证 #

合法串（可被接受） #

• 0：S→0→A，停在接受态
• 111：S→1→C→1→D→1→C，停在接受态
• 0001110：S→0→A→0→B→0→A→1→C→1→D→1→C→0→A，停在接受态

非法串（被拒绝） #

• 00：S→0→A→0→B，停在非接受态
• 001：S→0→A→0→B→1→Q，进入死状态
• 011：S→0→A→1→C→1→D，停在非接受态

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