构造语言W的补语言识别DFA的规则及状态转换疑问

首先明确原语言W的结构：
W是字母表{a,b,c,d,e,f,g}上所有满足以下条件的字符串：

• 以b开头
• 后续可重复添加任意次数的两种后缀：
  1. 任意多个（含0个）fe或ge拼接，再加上c
  2. e后接任意多个（含0个）a，再加上d
• 单独的b也属于W

补语言则是该字母表上不满足上述条件的所有字符串，包括：

• 不以b开头的字符串（含空串）
• 以b开头，但后续出现不符合规则的字符组合（比如b后直接跟a/d、f后未接e就出现c、d前不是e开头的a序列等）

补语言DFA的状态与转换规则 #

补语言DFA的状态转换逻辑和识别W的DFA完全一致，仅交换接受/非接受状态。具体规则如下：

状态定义

• q0：初始状态（未读取任何字符）
• q1：已读取合法前缀（以b开头，处于可添加合法后缀的状态）
• q2：刚读取f或g，等待读取e
• q3：刚读取e（属于Xd后缀的起始），等待读取a或d
• q4：已读取至少一组fe或ge，可继续读取f/g或c
• q_err：错误状态（已出现不符合W规则的字符组合）

状态转换规则

1. 初始状态q0
   • 读b → q1
   • 读a/c/d/e/f/g → q_err
2. 状态q1
   • 读f/g → q2
   • 读e → q3
   • 读c → q1
   • 读a/d → q_err
3. 状态q2
   • 读e → q4
   • 读a/b/c/d/f/g → q_err
4. 状态q4
   • 读f/g → q2
   • 读c → q1
   • 读a/b/d/e → q_err
5. 状态q3
   • 读a → q3
   • 读d → q1
   • 读b/c/e/f/g → q_err
6. 错误状态q_err
   • 读任意字符 → q_err

接受/非接受状态

• 接受态：q0、q2、q3、q4、q_err（这些状态对应的字符串都不在W中）
• 非接受态：q1（该状态对应的字符串属于W）

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