课程信息

• 授课教师： 卜磊
• 上课时间：2025秋

Finite Automata

• 自动机定义：
  • 有限个states(Q)
  • 一个输入字母表($\Sigma$)
  • 一个转移函数($\delta$) $\delta(q,a)$
  • 开始状态($q_0 \in Q$)
  • 结束状态集合(F)
  • $(Q,\Sigma,\delta,q_0,F)$
• 转移表

  • 	0	1
    A
    B
    C

• $...w,x,y,z$通常表示字符串,$a,b,c,...$表示单个输入符号
• 拓展$\delta$:$\delta(q,wa)=\delta(\delta(q,w),a)$
• $L(A)$是自动机$A$的语言
  • 如何证明自动机的描述性语言和自动机的表示语言相同：对于字符串长度进行归纳
• 如果$L$和某个DFA接受的语言相等那称为regular正则
  • 正则语言不能数数，不是正则的反例$\{0^n1^n|n\ge 1\}$
  • 反证法，若存在这样的DFA有$m$个状态，能够接受$0^m1^m$,那么对于前m个字符，必须要有$m+1$个状态，鸽笼原理可得有一个重复，则能够接受$0^{m'}1^m$
  • 同理，$\{w|w是平衡的括号序列\}$也不是
  • 但$\{w|w能被23整除\}$是
• 不确定性自动机
  • 同DFA，只是$\delta$的结果是一个集合
  • $NFA->DFA$: 子集构造法
  • 
• $\epsilon-NFA->NFA$
  • 设原来的转移函数是$\delta_E$,新转移函数$\delta_N$
  • $\delta_N(q,a)=\cup_{p\in CL(q)}\delta_E(p,a)$
  • $F'=\{q|CL(q)\land F\ne \emptyset\}$

Regular Expression

• *优先级最高，其次是连接，最后是+
• RE->NFA (对于每个表达式构造$\epsilon-NFA$)
• DFA->RE:
  • 对于DFA上的状态进行编号，1...n
  • k-PATH: 任意经过的状态编号都<=k，但起点和终点不受限制
  • 对于k-PATH的k进行归纳，证明路径可以被正则表达式表达
• 判定性质：
  • Membership(直接模拟)
  • Emptiness从开始状态找是否有可到达的结束状态
  • Infiniteness语言是否无限？
    • 如果DFA有n个状态，如果语言含有长度$>=n$的字符串，那语言无限（鸽巢原理）
    • 如果语言有$[n,2n-1]$长度的字符串，那语言无限（鸽巢原理）
    • 仍然效率感人，所以不如在消除死状态后判断是否有环
• 崩引理：对于每个正则语言$L$,存在一个整数$n$,对于每个$w \in L$长度大于等于$n$, 可以写出$w=xyz$，使得：
  • $|xy|\le n$
  • $|y|>0$
  • $xy^iz \in L, i\ge0$
• 继续判定性质：
  • Equivalence, 两个语言是否相等？构造乘积自动机，两个都是final states就接受
  • Containment，两个语言是否包含？构造乘机自动机，$[q,r]$中q是A的接受状态，r不是B的接受状态，如果这个乘积自动机为空说明是子集。
• DFA最小化：
  • 画出一个n*n的表格，如果一个状态是接受状态，一个状态不是，那么标记这两个状态是可区分的。
  • 继续，对于所有未标记的状态对，如果对于同一个输入到达的两个状态已经被标记可区分了，那么这两个状态也被标记为可区分。
  • 最后不能再继续标记的表格中，没有被标记为可区分的可以被合并
  • 最小化后可能会出现死状态，得继续消除。
  • 证明这样确实是最小的：
    • 假设确实有更小的B，则A,B起始状态不可区分（因为接受的字符串相同）
    • 根据归纳法，A中每个可达状态都在B中存在一个状态与其不可区分
    • 根据鸽巢原理，由于A状态数大于B，则A中有两个状态和B中的同一状态不可区分，传递性发现这两个状态也不可区分，矛盾。
• 正则语言的闭包性质：
  • Union（根据正则表达式）
  • 拼接和Kleene闭包(同样根据正则表达式)
  • Intersection （乘积自动机）
  • Difference（乘积自动机）
  • Complemention （$\Sigma^*-L$）
  • Reversal (在正则表达式上直接构造)
  • Homomorphism （在正则表达式上直接同态过去得到新表达式）
  • 逆同态
    • 构造一个新的DFA B，状态集合和A完全一致
    • 转移函数$\delta_B(q_0,w)=\delta_A(q_0,h(w))$
    • 可以对于w进行归纳

Context-Free Language

• Terminals 终结符号，Variables（非终结符号）变量，Start Symbol开始符号，产生式
• 如果$A \rightarrow \gamma$是一个产生式，那么我们说$\alpha A\beta=>\alpha \gamma \beta$; $=>^*$定义
• CFL语言可以数两个东西，但不能数三个
• BNF记号: 变量写在<...>里，多字符的终止符通常用加粗或者下划线表示while或者$\underline{WHILE}$,$::=$通常用于表示->,用$[...]$表示可选
• 最左推导，最右推导
• Parse Tree；叶子是终结符号或者$\epsilon$
  • Parse Tree和最左/最右推导等价
  • 对于树高进行归纳
  • 如果一个CFG能够推导出两个parse tree，那么其是一个二义性语法
  • 对于有些语法，二义性语法是不可避免的，如$\{0^i1^j2^k|i=j\ or\ j=k\}$
• CFL语言的化简
  • 无用变量(是否有变量不能推导出终结符)：从$A->w$逐步推导
  • 不可到达(是否有产生式不能从开始符号推导出来)：从$S$逐步推导
  • 去除Epsilon产生式（当然语言中不能有$\epsilon$）
    • 先找到nullable的变量(即$A=>^*\epsilon$)
    • 对于每个产生式$S->X_1X_2X_3..X_n$对于右边的每个可空变量，都考虑它是空或者不为空的情况(除去全为空，$2^n-1$种)
    • 证明对于推导步数进行归纳即可
  • 单元产生式$A->B$
    • 先找到单元对$(A,B)$,即$A=>^*B$全由单元产生式推导出（从$(A,A)$开始归纳）
    • 对于每个单元对$(A,B)$找到B的所有非单元产生式$B->\alpha$,将$A->\alpha$加入语法中
    • 删除所有单元产生式
  • 清理的时候先消除$\epsilon$产生式，再消除单元产生式，再消除无用变量，最后再消除不可达变量($epsilon$表达式消除后可能会产生单元表达式或者无用变量)
• CNF 乔姆斯基范式
  • $A->BC$或者$A->a$
  • 先清理文法，使得每个产生式都是只有一个终结符号或者$长度>=2$
  • 对于$>=2$的产生式，把所有终结符号都用变量代替
  • 然后切分成二元产生式，$A\rightarrow BCDE$ => $A\rightarrow BF, F\rightarrow ..$

Pushdown Automata

• PDA被以下定义：
  • 有限个状态 (Q)
  • 输入字母表 ($\Sigma$)
  • 栈字母表 ($\Gamma$)
  • 转移函数 ($\delta$)
  • 开始状态 ($q_0$)
  • 开始符号 ($Z_0 \in \Gamma$)
  • 接受状态 ($F$)
• 通常a,b,...是输入符号，...X,Y,Z是栈符号，...w,x,y,z是输入符号的字符串,$\alpha,\beta,...$是栈符号的字符串
• $\delta(q,a,Z)=(p,\alpha)$
• PDA的状态可以用$(q,w,\alpha)$描述,$q$是当前状态,$w$是剩余输出,$\alpha$是栈内内容
• ID I, ID j; I可以在PDA一步推导出J, $I \vdash J$
• 定义PDA语言的一种方法是用接受状态，$L(P)=\{w|(q_0,w,Z_0)\vdash ^*(f,\epsilon,\alpha))\}$
• 另一种方法是用空栈，$N(P)=\{w|(q_0,w,Z_0)\vdash ^*(q,\epsilon,\epsilon))\}$
• L(P)和N(P)表达能力相同:
  • $L(P)->N(P'):$P'会模拟P,如果$P$接受，那么$P'$会清空栈.在栈底加上一个保护性元素以防栈被其他时刻清空。
  • $N(P)->L(P'):$P'会模拟P，在栈底用一个保护性元素检测什么时候P清空栈，此时$P'$接受
• 确定性PDA没有不确定性自动机那么强大: 对于需要猜测的语言，如$ww^R$这样PDA需要猜测回文串的分隔位置，DPDA不能处理。可以为其提供一个决策依据$wcw^R$
• 正则语言一定能被DPDA表达
• DPDA的$L(P)$和$N(P)$不相等，因为DPA中的空栈一旦到达，就死机了（确定性原则）；如$\{0^n|n\ge 0\}$
• CFG->PDA:
  • 只有一个状态q
  • 输入符号是CFG的所有终结符号
  • 栈符号是CFG的所有符号
  • 起始符号是CFG的其实符号
  • $\delta(q,a,a)=(q,\epsilon)$ 把产生式的匹配转移到输入串上
  • $\delta(q,\epsilon,A)+=(q,\alpha)对于A->\alpha$ 展开产生式
  • 通过对PDA移动步数和最左推导进行归纳
• PDA->CFG
  • 使用$[pXq]$代表变量，该变量生成的字符串w，代表PDA从p开始，在读入w后进入状态q，并把栈顶符号X弹出
  • $\delta(p,a,X)包含(q,\epsilon)$,$[pXq]\rightarrow a$直接弹出
  • $\delta(p,a,X)包含(r,Y)$，$[pXq]\rightarrow a[rYq]$先读a进入状态r再到达q
  • $\delta(p,a,X)包含(r,YZ),[pXq]\rightarrow a[rYs][sZq]$
  • 起始符号$S$,并对于任何可能的状态$p$,添加产生式$S\rightarrow [q_0Z_0p]$ (空栈可以在任何状态被接受)

CFL&PDA

• 泵引理
  • 对于一个CFL$L$,存在一个整数$n$,对于每个在$L$中长度大于等于$n$的字符串$z$,存在$z=uwvxy$使得:
  • $|vwx|\le n$
  • $|vx|>0$
  • $uv^iwx^iy \in L$
  • $\{0^i10^i10^i|i\ge 1\}$
• Decision Properties:
  • Emptiness: 消除可空变量
  • Membership: CYK算法
    • $x_{i,j}$表示字符串中$[i,j]$能表示的变量
  • Infiniteness: 看看有没有长度在$[n,2n-1]$之间的字符串，有就无限
• 闭包性质
  • Union: 明显闭包
  • 拼接：明显闭包
  • Star：明显闭包
  • 反转： 封闭，把每个产生式都反转
  • 同态： 产生式把每个都换成同态后的结果
  • 交集: 不闭包
    • $\{0^n1^n2^n|n\ge1\}$不是CFL,但$\{0^i1^n2^n|n\ge1\}$和$\{0^n1^n2^i\}$都是，他们的交集是第一个，不是CFL。
  • 差： 不闭包
    • $L\cap M=L-(L-M)$
  • 但是CFL和正则语言的交集仍然是CFL
    • 将DFA和PDA并行运行，如果两个都接受才接受(如果遇上$\epsilon$则DFA状态保持不变)
  • 逆同态的证明
    • 构造PDA P', 接受$w$当且P接受$h(w)$ 就是在输入端用状态模拟出一个buffer
    • 状态是$[q,w]$,$q$是$P$的一个状态,w是$h(a)$的一个suffix
    • 开始状态时$[q_0,\epsilon]$,结束状态是$[f,\epsilon]$
    • $\delta'([q,\epsilon],a,X)=\{([q,h(a)],X)\}$从输入中获得buffer
    • $\delta'([q,bw],\epsilon,X)+=([p,w],\alpha)$如果$\delta(q,b,X)$包括$(p,\alpha)$消耗buffer

Turing Machine

• 图灵机
  • 有限个状态 (Q)
  • 输入字母表 ($\Sigma$)
  • 磁带字母表 ($\Gamma$)
  • 转移函数 ($\delta$)
  • 开始状态 ($q_0$)
  • 空白符号 ($B$)
  • 接受状态 ($F$)
  • $\delta(q,Z)=(p,Y,D)$ D是方向direction
  • 用$\alpha q\beta$表示一个状态，$\alpha \beta$代表从最左边非空到最右边非空的磁带,$q$指向刚刚被扫描的符号的左边，如果q在最右边，那么它在扫描B.
• $L(M)=\{w|q_0w\vdash^*I\}$,I包含一个final state或者从I没有可选的ID
• 证明二者相等：
  • final state->halting:
    • 对于每个final state，移除所有移动
    • 对于之前没有任何移动的非final state加上一个保护性的状态一直向后走
  • halting->final states
    • 添加一个新的final state
    • 对于之前没有停止的，转移到final state
• 用图灵机定义的语言叫做Recursively Enumerable Languages
• 我们称一个按终止状态接受的，一定能停下来的图灵机叫做算法，算法能接受的语言是Recursive Language
• Multiple Tracks多个磁道，同一个刺头
  • 可以用于标记位置
  • 用于存储数据
• 半无限磁道，开始位置往右为合法位置
• 可以用两个栈模拟一个磁带，一个栈记录磁头左边的位置，一个栈记录磁头和磁头右边的位置
• 用$2k$个磁道可以模拟k个磁带，一个磁道用来记录位置
• 非确定性图灵机NTM
  • 用DTM+队列模拟NTM
• Recursive & RE 语言的封闭性
  • Union: 用两个磁带并行地模拟
  • Intersection: 同样并行模拟
  • Difference: Recursive可以并行模拟，但RE不行，因此不封闭
  • 拼接：用一个两磁带的NTM，猜一个分割后并行模拟
  • Star: 同样，猜许多的分割
  • 反转：将输入反转再模拟
  • 同态：将输入同态后再模拟
  • 逆同态：构造一个NTM用于猜测x，使得$h(x)=w$

Decidability

• $decidable\subset RE\subset all\ language$
• 证明有些语言不是$RE$: 图灵机$countable$，但是所有语言$uncountable$
  • 语言不可数:取出每一位都不相同的字符串
  • 图灵机可数：任何由有限字符集组成的有限长度字符串的集合，都是可数的。
• 停机问题: $HALT=\{<M,x>|TM\ M\ halts\ on\ input\ x\}$
  • 不可判定
  • 假设$TM H$能够判定HALT
    • 如果$M$在$x$上停机，接受
    • 否则拒绝
  • 定义$H'$接受输入$<M>$
    • 如果$H$接受$<M,<M>>$则循环
    • 否则停机
  • 考虑$H'$接受输入$<H'>$,
    • 如果它停机，则证明$H$拒绝了$<H',<H'>>$,不能停机
    • 如果它不停机，则证明$H$接受$<H',<H'>>$,代表其必须停机
  • 冲突！！
• RE&Co-RE:
  • $Co-RE$是一个RE语言的补集
  • 如果一个语言既是RE又是Co-RE那么它是decidable
    • $decidable\rightarrow RE\ and\ Co-RE$ : 如果$L$可判定，那么其补集可以通过反转接受和不接受来实现decidable
    • $decidable\leftarrow RE\ and\ Co-RE$: 并行模拟两个已有的图灵机即可
• Complexity
  • TIme Complexity class: $TIME(t(n))=\{L|there\ exists\ a\ TM\ M\ that\ decides\ L\ in\ time\ O(t(n))\}$
  • 对于多磁带的TM，每个$t(n)$有等价的$O(t(n)^2)$的单磁带$TM$
  • $P,NP$的定义:
  • $L=\{x|\exists y,｜y｜\le|x|^k,<x,y>\in R\}$ 则$L\in NP$
  • CLIQUE问题
• 规约
  • 给出一个新问题$NEW$,我们想判定它是否$undecidable$, 可以从一个已知的不可判定问题$OLD$转化到$NEW$,能够解决$NEW$的解法也可以用于解决$OLD$
  • 如果我们想证明$A_{TM}=\{<M,w>:M\ accepts\ input\ w\}$不可判定：
    • 那我们得假设A可判定，然后用A解决HALT问题
    • $<M,w> \in A_{TM}$ 如果是的话那说明肯定HALT，如果不接受说明要么$M$拒绝$w$或者$M$在$w$上不停机
    • 交换$M$中的接受和拒绝状态，再次判定，如果是的话说明肯定是拒绝，HALT；否则不是HALT
  • $Rice's\ Theorem$一切不平凡的TM性质都是$undecidable$的！
  • NP问题的规约，SAT,3SAT问题