## Chapter 1
拜伦：第一个给计算机写程序的人；图灵：人工智能之父、计算机科学之父、**计算机之父**；拜伦：现代计算机之父、博弈论之父；巴贝奇：差分机、分析机；丘奇：可计算理论
关系：$R\subset A\times B$；等价关系：自反、传递、对称
半群：(S,\*)，其中\*是满足**结合律**的二元运算. 若*还满足交换律，则为**交换半群**
同构：(S,\*)和(T,$\circ$)是半群，若$f:S\to T$是双射且$f(a*b)=f(a)\circ f(b)，\forall a,b\in S$
* 同构四步骤：选f使得Dom(f)=S，f单，f满，$f(a*b)=f(a)\circ f(b)$
通路（边顺次相连）、路径（无重复边）、简单路径（无重复点）、树高（从0层开始）
字符串前缀后缀包括空串
$|\{\epsilon\}|=1，|\epsilon|=0$
## Chapter 2
M接受的语言：$L(M)=\{w\in \Sigma^*: \delta^*(q_0,w)\in F \}$
## Chapter 3
w被NFA接受：存在一条路径接受w
w被NFA拒绝：NFA中不存在接受w的路径（对于每个路径，要么字符串输完不在终态，要么无法输完）
注意与DFA不同点：$\epsilon$也可以作为输入、$\delta:Q\times \Sigma\cup\{\epsilon\}\to 2^Q$映射到状态的**幂集**
状态转移是集合↑
扩展转移函数（老麻烦了）：**与DFA相比，函数映射到一个集合**
$\delta^*(1,b)=\{3,4,5,6,7\}$
$\delta^*(1,bb)=\{4\}$
$\delta^*(1,ba)=\{3,4,5,6,7\}$
## Chapter 4
单一终态的NFA：**任何NFA都等价于一个只有一个终态的NFA**（将所有终态用$\epsilon$转移到一个状态）
正则语言的封闭性：
*补要用DFA，原因是NFA一些因为没有合适转移的串在补的NFA里也没有合适转移；因此要用有明确转移的DFA*
正则表示的定义：**三个基础、四个归纳形式**（基础不要忘了$\varnothing$）
运算符优先级：* 、· 、+
正则表示的语言定义：对语言从上面三个基础、四个归纳形式来定义
没有两个连续0的字符串：(1+01)*(0+$\epsilon$)
01交替的字符串：(0+$\epsilon$)(10)*(1+$\epsilon$)
证明正则表示语言=正则语言：前推后从正则表示定义和正则语言封闭性，反推用状态消去构造
$r=r_1^*r_2(r_4+r_3r_1^*r_2)^*$
正则语言的同态：$h:\Sigma\to T^*$拓展为$h(w)=h(w_1)\cdots h(w_n)（w=w_1\cdots w_n）$
逆同态（映射到字符串集合）:$h^{-1}(L)=\{w|w\in \Sigma^*\wedge h(w)\in L\}$
定理1：若L是正则语言，则h(L)也是正则语言
定理2：若L是正则语言，则h^-1^(L)也是正则语言
正则表示：连接运算的单位元是$\epsilon$，**零元是$\varnothing$**；并运算单位元是$\varnothing$
## Chapter 5
句子/句型
推导闭包$\xRightarrow{*}$
$L(G)=\{w|S\xRightarrow{*}w,w\in T^*\}$
线性文法：产生式右侧最多一个变量，要么没变量，剩下的均是终结符串
右线性文法：产生式右侧要么没变量，有变量则至多一个且在最右侧
***正则文法（3型文法）***：左线性文法或右线性文法（二者只能出现一个）
NFA转化为右线性文法易错点：
积自动机，注意是DFA，语言是两个语言的并
注意F、S、$\delta$
## Chapter 6
判定算法：
* w是否能被接受：DFA O(n) / NFA O(ns^2^) / 正则表达式转化为NFA
* 正则语言是否为空：DFA O(S) / 正则表达式 O(n)(符号数)
* 判断两个正则语言是否相等：转化为DFA，两个DFA并起来，用填表法看两个初态是否可区分O(n^2^)
* 正则语言是否无限：DFA初态到终态是否存在环
***泵引理***：$(\forall m)( \exists w)(w\in L\wedge |w|\ge m\wedge( \forall x,y,z)(\exist k) (xyz=w\wedge |xy|\le m\wedge y\neq \epsilon \rightarrow xy^kz\notin L) )$
**注意k的选取可以与m,w,x,y,z有关，一般常用m、|y|**
泵引理不是充分条件，而是必要条件
## Chapter 7
DFA状态集等价关系：$p,q\in Q, pRq\quad iff\quad \delta^*(p,w)\in F\Leftrightarrow \delta^*(q,w),\forall w $
填表算法：基础是p终态、q非终态标记可区别；归纳定义状态r、s通过某个符号a转移到可区别的两个状态，则r、s可区别
最优的DFA：用填表法计算出等价类后进行划分；可以反证状态数比M少的自动机来证明最优
归约：$v+d\Rightarrow E+d\Rightarrow EOd\Rightarrow EOE\Rightarrow E$，推导$E\Rightarrow v+d$
最左推导，最右推导：每次都替换最左/右侧的非终结符
左句型：$S\xRightarrow[lm]{*}\alpha$
语法分析树：内部节点非终结符、**叶节点为终结符或非终结符**，如果叶节点$\epsilon$则为父节点唯一子节点
证明某语言是某文法的语言：要正反两方面说包含关系
## Chapter 8
文法二义性：**存在某字符串**有至少两种最左（或最右）推导$\Leftrightarrow$存在两棵不同的分析树
一个CFG是否为二义的问题是不可判定的
固有二义：CFL的所有文法均是二义的（不存在无二义文法）
题目：${n_0=n_1}$
## Chapter 9
栈可以为空（可以把栈底符号弹出来），但空栈以后就不可以转移了
转移时可以有$\epsilon,\epsilon\to \epsilon$
PDA是非确定的，转移的是一个集合
$\Sigma和\Gamma$不一定无交
终态型PDA接受字符串：所有字符串输入完毕且落在一个终态上
即时描述$(q,w,\alpha)$，其中w是还未输完的串，$\alpha$是栈底符号串；传递和传递闭包$\vdash、\vdash^*$
终态型PDA语言：$\{w|(q_0,w,Z_0)\vdash ^* (q_f,\epsilon, \alpha),q_f\in F,\alpha\in \Gamma^*\}$
空栈型PDA语言：$\{w|(q_0,w,Z_0)\vdash ^* (q,\epsilon, \epsilon),q\in Q\}$
总结，都要添加一个状态并且**改栈底符号为$X_0$**，添加转移$\epsilon,X_0/ Z_0X_0$
添加$\delta(q,\epsilon,S)=\{(q,\Sigma^*)\}$，注意添加$\delta(q,v,v)=\{(q,\epsilon)\}$
## Chapter 10
确定下推自动机：与PDA只有转移函数上的不同
* **约束**：**栈顶符号不能为空**、**输入符号为空和不为空互斥**（只能有一个）、转移的状态唯一
**注意输入符号为空的互斥条件仅限于相同栈顶元素的条件下**：
* $\delta(q,\epsilon,X)与\delta(q,a,X)$互斥
* $\delta(q,\epsilon,X)与\delta(q,a,Y)$不互斥
确定性上下文无关语言：终态型DPDA语言
$\{0^n1^n|n\ge 1\}$既是终态型DPDA语言，也是空栈型DPDA语言
$\{ww^R\}$不是DPDA语言，证明了DPDA$\alpha$———>√
$\beta$———>×
**化为Chomsky范式**
Chomsky范式**（CNF）**：1）G中不含无用符号；2）产生式P只有两种形式：$A\to BC\ /\ A\to a$
注意：消除无用符号可以在其中穿插反复进行
## Chapter 11
CFL泵引理：
$\forall m\exists z(z\in L\wedge |z|\ge m\wedge(\forall u,v,w,x,y)(\exists k)(z=uvwxy\wedge vx\neq \epsilon \wedge |vwx|\le m\to uv^kwx^ky\notin L))$
例子：$\{ww\}、\{0^n1^n2^n\}$不是CFL
**CFL封闭运算：**并、星闭包、连接、反转
**非封闭运算：**交、补、差
替换：$s:\Sigma\to \mathcal{L}$
定理：设$\forall a\in \Sigma , s(a)是CFL$，若L是$\Sigma$上的CFL，则s(L)是CFL
定理：设L是CFL，则h(L)（h^-1^(L) ）均是CFL
**正则闭性质：CFL和正则语言的交为CFL**（在此基础上**交运算**也封闭）
例题：$L=\{a^nb^n|n\neq 100\}$是CFL，取正则语言L={$a^{100}b^{100}$}，它的补为L={$w|w\neq a^{100}b^{100}$}，与CFL$\{a^nb^n\}$交得证
例题：$L=\{n_an_bn_c\}$不是CFL，假设成立，取正则语言$\{a^*b^*c^*\}$归谬，二者交为$\{a^nb^nc^n\}$是CFL，显然不正确
## Chapter 12
空语言问题：检查语言是否为空，则判断开始变量是否无用
无限语言问题：进行CFG的化简，之后构造变量依赖图，判断是否有环
语言元素问题：**CYK解析算法 O(n^3^)**
CFL不可判定问题：
CFG是否歧义、CFL是否固有二义、CFL相交是否为空（交自动机）、CFL是否相等（并自动机看初态是否可区分）、CFL是否是$\Sigma^*$
TM的注意事项：
* 初始时读头位于输入串最左
* 输入串不为空
* TM机默认是确定TM的
* 状态转移是一个元素（三元组）而非集合，不允许$\epsilon$转移
* 接受输入：输入完字符串，TM停在某终态（反之停在非终态、进入无限循环（我们假定到终态即停机，可以证明任何一个图灵机都等价于一个到终态即停机的TM））
* 注意，图灵机可以不接收完输入串
总结一下：状态右边一定要有符号，与状态右边无关的空白符可以删去
**递归可枚举语言：**有定理称任何图灵机都可以转化为到达终态就停机的图灵机（根据原来的定义，有可能还会继续，以后假定到达终态一定停机
**递归语言**：对于任何不属于L(M)的字符串也可以使得M停机。递归语言对应的问题是可判定的。
## Chapter 13
单位制：00000（十进制的5）
f可计算：$\forall w\in D,有f:q_0w\vdash^* q_ff(w)$，例如$f(x,y)=x+y$，输入x1y则输出xy1（单位制下）
**计算后要回到初始状态**
相当于对**状态**进行扩展，扩展为q'=[q,a,b,c]，但存储区只能有有限个
相当于对**带符号**进行扩展，带符号变为[X,Y,Z]
多带图灵机：第一条带处于输入符号的最左端，其余读头任意放置；**k条带可用2k通道的TM模拟**
语言L$\{a^nb^n\}$；标准图灵机O(n^2^)，2带O(n)
2维TM用二通道模拟
非确定图灵机：转移映射到一个三元组集合
可以用一个二维图灵机模拟，每一步复制当前结构并改变副本中的状态
**两道半无限带机**可以模拟TM
**多栈机**
k个栈的多栈机可以用k+1个带的多带图灵机模拟（其中一个用来扫描输入）
一个双栈机可以模拟标准图灵机：一个堆栈模拟读头左边单元格，一个模拟右边
**计数器机**
计数器机只有两个栈符号$Z_0,X$，$X$只能被替换为$X^i$，$Z_0$只能被替换为$X^iZ_0$
**定理**：一个计数器的计数器机语言接受能力相当于确定下推自动机KDPA；两个相当于图灵机
## Chapter 14
**图灵机编码**：
假定
* 字母表为0,1
* 初态1，终态2
* 带符号 0编码1 1编码2 B编码3
* 带头移动 L编码1 R编码2
**输入字符串w编码**：1w，(Eg: 0000000对应128个输入字符串)
对角线语言：$L_d=\{w_i|w_i\notin L(M_i)\}$，不是递归可枚举语言
通用语言：$L_U$ $M_i111w_i$，递归可枚举语言
***语言非空图灵机是不可判定的，但是是RE的***
则语言为空图灵机非RE
RICE引理描述的是图灵机编码的性质，即它是将一些接受特定语言的图灵机挑出来
* 一台图灵机接受的语言是否是正则语言/CFL均是不可判定的
定理：
* 递归语言的补也是递归语言
* 若语言L和L的补都是递归可枚举语言，则二者均是递归语言
定义：
* 若一个问题对应的语言是递归语言，则可判定，否则不可判定
* 若一个问题对应的语言是递归可枚举语言，则称为**部分可判定**
问题P1到P2的简约：$P_1\le_T P_2$，则$P_2可判定/部分可判定\Rightarrow P_1也；P_1不可判定/非RE\Rightarrow P_2也$
图灵机停机问题：任给图灵机M和字符串w，问是否停机——不可判定
该问题不是可判定问题
非确定图灵机时间复杂度：树高
复杂度归约$P_1\le _P P_2$
* 若P2是P问题，则P1也是；**若P2是NP问题，则P1也是**
* **若P1不是P问题，则P2也不是；若P1不是NP问题，则P2也不是**
NP-hard：任何一个NP问题都可以简约到该问题上
如果可以证明某个NPC是P的，则有P=NP