计算理论
可能的大题：
- 证明RL：
- RL运算封闭性：hw2-1
- NFA/DFA图示：小测1-2，hw2-3
-
Pumping theorem：hw2-6
- 要理解证明思路，知道如何构造反例证明不是RL，关键在于字符串xyz长度的选取和i的选取（比如取0）
-
构造NFA/DFA：注意定义状态变量时应赋予其实际含义，比如q0表示模3的结果为0
-
证明CFL：
-
PDA/CFG：hw3-1~3，小测2-1
-
NP：
- NP理论：hw4-1~4
-
证明是NP问题：hw4-3
- 明确NP定义：F\in NP: F(x)=1 == 存在poly-time verifier V and certificate c, s.t. V(c,x)=1 存在poly-time TM M_F that decides F.
-
可计算性：
- 可计算：hw3-2(construct a TM that computes it)
- 不可计算：
- Rice theorem：小测2-2(non-trivial and semantic)
- 规约：使用反证法，如果该函数可计算则HALT/HALTONZERO/ZEROFUNC可计算，也就是把已知的这几个不可计算函数规约到新函数。 常用手段为构造M'，使M'满足性质P iff M halts on x/M halts on zero/M computes zero function
- 规约：
- 小测2-3
- 作业