请问我设计的DFA是否正确接受语言L的补语言？

首先明确目标：我们要验证的DFA需要接受的是$\boldsymbol{\overline{L} = { w \in {0,1}^* : 01不是w的子串 }}$，也就是所有不含"01"子串的0-1字符串。这类字符串的结构很清晰：要么是空串，要么是全1组成的串，要么是若干个1（可以没有）后面跟着若干个0的串——一旦出现0之后就不能再出现1，否则就会形成"01"子串。

你可以对照以下几点检查你的DFA是否正确：

• 状态划分是否合理：
  • 必须包含初始状态（未遇到过0的状态）、已遇到过0但未触发01的状态、触发01后的死状态这三类核心状态
• 状态转移是否符合规则：
  • 初始状态：输入1时保持在初始状态；输入0时转到已遇0的状态
  • 已遇0的状态：输入0时保持在该状态；输入1时转到死状态
  • 死状态：输入0或1都保持在死状态，不再转移
• 接受状态设置是否正确：
  • 初始状态（对应空串、全1串）和已遇0的状态（对应全0串、1...10...0串）必须设为接受状态
  • 死状态必须设为非接受状态

如果你的DFA完全符合上述要求，那它就能正确接受$\overline{L}$，而DFA识别的语言都是正则语言，这也就证明了$\overline{L}$是正则语言。

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