如何绘制两类指定规则的DFA？含czccz、不含ammam的自动机

通用设计核心 #

所有针对“是否包含/不包含某固定子串”的DFA，都可以通过最长已匹配前缀法简化设计：状态仅记录当前位置之前的输入中，能和目标子串匹配的最长前缀长度，每次输入新字符时，重新计算最长匹配长度并跳转对应状态，无需额外冗余状态。判定规则上：

• 匹配“包含目标子串”的语言：完整匹配目标子串的状态是唯一终态，进入该状态后所有输入都留在该状态自环
• 匹配“不包含目标子串”的语言：除了完整匹配目标子串的状态（非接受态）之外，其余所有状态都是接受态，进入非接受态后所有输入都留在该状态自环

第一类：包含子串czccz的DFA设计 #

状态定义 #

在题目给出的5个匹配前缀状态基础上，补充初始状态与终态，共6个状态：

• S0：初始状态，已匹配最长目标串前缀长度为0（此前输入无有效匹配目标串起始c的内容）
• S1：已匹配最长前缀为c（目标串第1位匹配成功）
• S2：已匹配最长前缀为cz（目标串前2位匹配成功）
• S3：已匹配最长前缀为czc（目标串前3位匹配成功）
• S4：已匹配最长前缀为czcc（目标串前4位匹配成功）
• S5：已完整匹配子串czccz（唯一终态）

转移箭头规则 #

按每个状态遇到字符c、z的跳转逻辑逐一绘制：

1. S0的转移
   • 输入c：匹配到目标串第1位，跳转至S1
   • 输入z：未匹配到目标串起始字符，在S0自环
2. S1的转移
   • 输入z：拼接为cz，匹配目标串前2位，跳转至S2
   • 输入c：拼接为cc，取最长匹配后缀（单个c，匹配目标串第1位），在S1自环
3. S2的转移
   • 输入c：拼接为czc，匹配目标串前3位，跳转至S3
   • 输入z：拼接为czz，无匹配目标串的有效前缀后缀，跳转回S0
4. S3的转移
   • 输入c：拼接为czcc，匹配目标串前4位，跳转至S4
   • 输入z：拼接为czcz，取最长匹配后缀（cz，匹配目标串前2位），跳转至S2
5. S4的转移
   • 输入z：拼接为完整目标串czccz，跳转至终态S5
   • 输入c：拼接为czccc，取最长匹配后缀（单个c，匹配目标串第1位），跳转至S1
6. S5的转移
   • 无论输入c还是z，都在S5自环（只要出现过一次目标子串，后续输入不会改变“包含目标串”的判定结果）

第二类：不包含子串ammam的DFA设计 #

状态定义 #

共6个状态，其中仅1个为非接受状态：

• S0：初始状态，已匹配最长目标串前缀长度为0，接受状态
• S1：已匹配最长前缀为a（目标串第1位），接受状态
• S2：已匹配最长前缀为am（目标串前2位），接受状态
• S3：已匹配最长前缀为amm（目标串前3位），接受状态
• S4：已匹配最长前缀为amma（目标串前4位），接受状态
• Sbad：已完整匹配子串ammam，唯一非接受状态

转移箭头规则 #

1. S0的转移
   • 输入a：匹配到目标串第1位，跳转至S1
   • 输入m：未匹配到目标串起始字符，在S0自环
2. S1的转移
   • 输入m：拼接为am，匹配目标串前2位，跳转至S2
   • 输入a：拼接为aa，取最长匹配后缀（单个a），在S1自环
3. S2的转移
   • 输入m：拼接为amm，匹配目标串前3位，跳转至S3
   • 输入a：拼接为ama，取最长匹配后缀（单个a），跳转至S1
4. S3的转移
   • 输入a：拼接为amma，匹配目标串前4位，跳转至S4
   • 输入m：拼接为ammm，无匹配目标串的有效前缀后缀，跳转回S0
5. S4的转移
   • 输入m：拼接为完整目标串ammam，跳转至非接受态Sbad
   • 输入a：拼接为ammaa，取最长匹配后缀（单个a），跳转至S1
6. Sbad的转移
   • 无论输入a还是m，都在Sbad自环（只要出现过一次目标子串，后续输入不会改变“包含目标串、不符合语言要求”的判定结果）

DFA练习优质站点推荐 #

可通过公开搜索引擎查找以下类型的练习工具，无需直接访问外链：

• 自动机可视化模拟工具：支持输入正规式自动生成DFA/NFA，可逐字符模拟状态转移过程，实时校验转移逻辑的正确性
• 高校公开的自动机课程习题模块：附带常见子串匹配类题目的参考设计思路，完成练习后可直接对比转移表排查错误
• 通用流程图绘图工具：支持拖拽状态节点、标注转移箭头，方便快速排版DFA结构，导出高清设计稿

内容的提问来源于stack exchange，提问作者José Manolito