时间复杂度一题都没考，卷子简单到几乎不需要大抄。

  1. 给了一个两个子句两个变量的 3SAT，是否可满足？
  2. 构造满足至少两个 0 且至多一个 1 的 DFA
  3. NFA → DFA
  4. NFA → regex
  5. 给一个 CFG
    1. 是否存在歧义？
    2. 转换为乔姆斯基范式
  6. 证明无限 0 1 序列 B 是不可数的
  7. 证明 $EQ_{TM}$ 不是图灵可识别的