如何构造接受语言L的DFA：含'110'且不含'010'

核心思路 #

先明确语言的两个约束：

• 必须包含子串 110
• 绝对不能包含子串 010

构造DFA的关键是跟踪当前输入的后缀，同时记录两个状态：是否已经出现过110，以及是否违反了“不包含010”的规则。

分步构造提示 #

1. 定义基础状态（未出现110且未违反规则） #

• S0：初始状态，无有效后缀，未出现110，未违反规则
  • 输入0 → S1（当前后缀为0）
  • 输入1 → S2（当前后缀为1）
• S1：当前后缀为0，未出现110，未违反规则
  • 输入0 → S1（后缀更新为00）
  • 输入1 → S3（后缀更新为01）
• S2：当前后缀为1，未出现110，未违反规则
  • 输入0 → S1（后缀更新为10）
  • 输入1 → S4（后缀更新为11）
• S3：当前后缀为01，未出现110，未违反规则
  • 输入0 → D（触发010，违反规则，进入死状态）
  • 输入1 → S2（后缀更新为11）
• S4：当前后缀为11，未出现110，未违反规则
  • 输入0 → S5（首次出现110，进入接受状态分支）
  • 输入1 → S4（后缀保持11）

2. 定义接受状态分支（已出现110且未违反规则） #

这部分状态需要确保后续输入不会产生010：

• S5：已出现110，当前后缀为0（110的最后一位），属于接受状态
  • 输入0 → S6（后缀更新为00）
  • 输入1 → S7（后缀更新为1）
• S6：已出现110，当前后缀为00，接受状态
  • 输入0 → S6
  • 输入1 → S8（后缀更新为01）
• S7：已出现110，当前后缀为1，接受状态
  • 输入0 → S6（后缀更新为10）
  • 输入1 → S7（后缀保持11）
• S8：已出现110，当前后缀为01，接受状态
  • 输入0 → D（触发010，违反规则）
  • 输入1 → S7（后缀更新为11）

3. 定义死状态 #

• D：一旦输入触发010，进入此状态，所有输入都停留在D，且此状态为非接受状态

4. 标记接受状态 #

所有已出现110且未进入死状态的状态（S5、S6、S7、S8）都是接受状态。

验证小技巧 #

• 测试包含110但不含010的字符串，比如110、1101、00110，检查是否能走到接受状态
• 测试包含010的字符串，比如010、11010，检查是否会进入死状态
• 测试未包含110的字符串，比如011、101，检查是否停留在非接受状态

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