DFA可识别语言补集求解咨询：Σ={a,b}，原语言含字符a

首先明确补集的定义：字母表Σ上的语言L的补集$\overline{L}$，是所有属于Σ*（Σ上所有有限长度字符串的全集）但不属于L的字符串集合。

原语言$L = {w \mid w \text{ 包含至少一个 } a}$，它的补集可以直接表示为：

$\overline{L} = \{w \mid w \text{ 中不含任何 } a\}$

换个更直观的写法：补集是由任意数量（包括0个）的b组成的字符串集合，也就是${b^n \mid n \geq 0}$，其中$b^0$对应空串$\epsilon$。

关于b是否属于补集： #

• b里没有a，不属于原语言L，所以必然属于补集$\overline{L}$。
• 你判断a不属于补集是对的，因为a包含a，属于原语言L。

补集对应的DFA逻辑（无需图也能理清）： #

原DFA的状态分为两种：未读到过a的初始状态（原DFA的非接受态）、读到过a的状态（原DFA的接受态）。要构造补集的DFA，只需要把原DFA的接受态和非接受态互换：

• 初始状态变为接受态，读任意个b都保持在这个接受态；
• 一旦读到a，就进入非接受态，之后无论读a还是b都维持非接受态。

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