正则表达式^[ab]?|c?$的可接受字符串及DFA绘制咨询

首先明确你描述的正则对应的匹配规则：匹配空字符串，或以a/b开头的任意字符串，或以c结尾的任意字符串。

先明确哪些字符串不被接受 #

反向推导更清晰：不被该正则匹配的字符串必须同时满足三个条件：

• 不是空字符串
• 开头既不是a也不是b
• 结尾不是c

典型的不匹配例子：

• 单个非a/b/c的字符：d、x
• 多字符且开头非a/b、结尾非c：xdx、yzz、pqrs

DFA构建思路 #

你可以把整个匹配逻辑拆成基于关键条件的状态流转，核心跟踪两个判断：是否已经满足「开头为a/b」，以及当前结尾是否是c。

设计状态如下：

• S0（初始+接受状态）：对应空串，未输入任何字符
• S1（接受状态）：已输入a或b作为开头（一旦进入此状态，后续无论输入什么都保持在此状态，因为已满足匹配条件）
• S2（非接受状态）：输入过字符，但既没满足开头a/b，当前结尾也不是c
• S3（接受状态）：当前结尾是c（不管前面是什么，只要最后一个字符是c就满足匹配）

状态转移规则：

1. 从S0出发：
   • 输入a或b → 进入S1
   • 输入c → 进入S3
   • 输入其他字符 → 进入S2
2. 从S1出发：
   • 输入任意字符 → 留在S1
3. 从S2出发：
   • 输入c → 进入S3
   • 输入其他字符 → 留在S2
4. 从S3出发：
   • 输入c → 留在S3
   • 输入其他字符 → 进入S2

所有最终停在S2的字符串就是不被接受的，停在S0、S1、S3的字符串均为匹配的目标字符串。

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