DFA (确定有限自动机)
M=\( (Q, \Sigma, \delta, q_0, F) \). \( \delta:Q \times \Sigma \to Q \). \( \hat{\delta}(q,\varepsilon)=q \), \( \hat{\delta}(q,wa)=\delta(\hat{\delta}(q,w),a) \). \( L(M)=\{w \mid \hat{\delta}(q_0,w) \in F\} \)
正则语言对∪,∩,补,∘,*,反转封闭. 乘积DFA: F₁∪₂=(F₁×Q₂)∪(Q₁×F₂); F₁∩₂=F₁×F₂; 补=交换F. 最小化:去不可达→迭代分裂不等价组→唯一最小DFA
NFA → DFA (子集构造)
\( \delta:Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q) \). ε-闭包E(S)=S出发仅经ε可达的状态(BFS). NFA接受:∃一条计算路径到接受状态
子集构造:初始=E({q₀}); δ_D(R,a)=E(∪_{r∈R}δ_N(r,a)); F_D={R|R∩F≠∅}. n状态NFA→≤\( 2^n \)状态DFA(上界可达). NFA≠更强,但更简洁
正则表达式 ⟷ NFA ⟷ DFA
R→NFA(Thompson):基元=边;并=ε分叉+汇;连=串联;星=ε回路+旁路. DFA→R(GNFA):加始终→逐消中间态→新边=R₁(R₃)*R₂∪R₄→剩一边即R
优先级:*>∘>∪. R∪S=S∪R; (R*)*=R*; ∅*=ε; R∪∅=R; R∅=∅R=∅; R(S∪T)=RS∪RT. 常用: (0∪1)*(全), (0∪1)*1(0∪1)*(含1)
泵引理 ★必考
L正则⇒∃p: ∀w∈L(|w|≥p) ∃w=xyz: |xy|≤p, |y|>0, ∀i≥0:xyⁱz∈L
证非正则:①假设正则(泵长p)②选w∈L,|w|≥p,利用|xy|≤p限制y位置③取某i使xyⁱz∉L. 关键:w依赖p;用|xy|≤p限制y落点.
{0ⁿ1ⁿ}: w=0ᵖ1ᵖ, y=0ᵏ, i=2→0^{p+k}1^p∉L. {ww}: w=0ᵖ10ᵖ1, y在前半. {a^q|q素数}: i=q+1→a^{q(1+k)}合数. {0ⁱ1ʲ|i>j}: i=0下泵.
Myhill-Nerode: L正则⟺x∼_L y有有限等价类. 类数=最小DFA状态数. 证非正则:找无限等价类({0ⁱ}对{0ⁿ1ⁿ}). 闭包性: L∩R非正则(R正则)⇒L非正则.
图灵机 (TM)
M=\( (Q,\Sigma,\Gamma,\delta,q_0,q_{\text{acc}},q_{\text{rej}}) \)七元组. δ:Q×Γ→Q×Γ×{L,R}. 格局=u q v(带uv,状态q,头在v首). 在q_acc/q_rej停机
多带TM:k带δ:Q×Γᵏ→Q×Γᵏ×{L,R}ᵏ,O(t²)单带模拟. NTM:δ→P(Q×Γ×{L,R}),存在接受分支即接受. 枚举器:L可识别⟺L可枚举. Church-Turing:"算法"=TM. UTM可模拟任意TM
可判定 vs 可识别
| 可判定(Decidable) | 可识别(RE) |
|---|
| TM在所有输入停机 | TM在接受串停机接受;拒绝可能loop |
| L和L̄都可识别⇒L可判定 | \( A_{\mathsf{TM}} \)可识别但不可判定 |
\( A_{\mathsf{TM}} \)不可判定 ★
\( A_{\mathsf{TM}} \)={⟨M,w⟩|M接受w}. 可识别(UTM)但不可判定
对角化:假设H判A_TM→构D(⟨M⟩):跑H(⟨M,⟨M⟩⟩)→H接受则D拒绝反之. D(⟨D⟩)接受?⟺H(⟨D,⟨D⟩⟩)拒绝⟺D(⟨D⟩)拒绝. 矛盾! ∴H不存在∎
推论:TM可数(有限描述)→语言不可数(Σ*子集≈R)→绝大多数语言不可识别!
不可判定问题链
| 问题 | 可识别? | 归约 |
|---|
| \( A_{\mathsf{TM}} \) | ✓(UTM) | 对角化(源) |
| HALT_TM | ✓ | \( A_{\mathsf{TM}} \)≤_m:M′模拟M,若M接受→停,否则loop |
| E_TM | 补可识别 | \( A_{\mathsf{TM}} \)≤_m:M′对入x:若x≠w拒,若x=w模拟M |
| EQ_TM | ✗ | E_TM≤_m |
| REGULAR_TM | ✗ | Rice定理 |
| ALL_TM(L(M)=Σ*) | ✗ | Rice定理 |
映射归约 \( A \leq_m B \)
∃可计算f:w∈A⟺f(w)∈B. ≤_m传递. A不可判定∧A≤_mB⇒B不可判定. A不可识别∧A≤_mB⇒B不可识别
Rice定理 ★
P为RE语言的非平凡语义性质⇒L_P={⟨M⟩|L(M)满足P}不可判定
证:归约自A_TM,设∅∉P,取M_P满足P,构M′先模拟M→若接受转模拟M_P. L(M′)=L(M_P)∈P当M接受w;否则=∅∉P.
推论(均不可判定):{⟨M⟩|L(M)正则/有限/无限/∈CFL/含ε/=Σ*}. 不适用:语法性质("状态数<5")
语言类层次
\( \mathsf{REG} \subsetneq \mathsf{CFL} \subsetneq \mathsf{DEC} \subsetneq \mathsf{RE} \subsetneq \mathsf{ALL} \)
{0ⁿ1ⁿ}∈CFL\Reg. A_TM∈RE\Dec. A̅_TM∈All\RE. 可判定性:DFA全可判;CFG成员/空可判,等价不可判;TM全不可判(Rice)
| 问题 | DFA | CFG | TM |
|---|
| 成员 | ✓(模拟) | ✓(CYK O(n³)) | ✗ |
| 空性 | ✓(BFS) | ✓(标记法) | ✗ |
| 等价 | ✓(对称差) | ✗ | ✗ |
| 全性 | ✓ | ✗ | ✗ |
时间复杂性: P / NP
TIME(t)={L|DTM在O(t)判定}. P=∪_k TIME(nᵏ). NP=∪_k NTIME(nᵏ). EXPTIME=∪_k TIME(2^{nᵏ})
NP验证机刻画:L∈NP⟺∃多项式p,V: x∈L↔∃c(|c|≤p(|x|))∧V(x,c)=1. P⊆NP⊆EXPTIME. P=?NP open
时间层次:f(n)log f(n)=o(g(n))⇒TIME(f)⊊TIME(g). 推论:P⊊EXPTIME. Cook-Levin: SAT是NPC
NPC归约链
SAT→3SAT→CLIQUE→IS→VC→SUBSET-SUM; 3SAT→HAMPATH
| 归约 | 要点 |
|---|
| SAT→3SAT | 长句(a∨b∨c∨d)→(a∨b∨x)∧(¬x∨c∨d) |
| 3SAT→CLIQUE | 每文字→顶点,不矛盾不同句文字间连,k=子句数 |
| CLIQUE→IS | 取补图; G的团=Ḡ的独立集 |
| IS→VC | S独立⟺V\S点覆盖; k_VC=n-k_IS |
| →SUBSET-SUM | 高基数编码,每变量(真/假)两数,每子句两数,列和约束 |
NPC证明四步 / coNP
NPC:①L∈NP(证书+验证器)②选已知NPC源(3SAT)③构造多项式f④证双条件(⇒和⇐)
coNP={L|L̄∈NP}. TAUTOLOGY,UNSAT. NP?=coNP open. NP≠coNP⇒P≠NP. 若NP=coNP→PH坍缩
| 问题 | 证书 | 验证 |
|---|
| SAT | 赋值τ | 代入 O(n) |
| CLIQUE | k顶点 | 完全子图 O(k²) |
| HAMPATH | 顶点序列 | 每步有边 O(n) |
| SUBSET-SUM | 子集 | 求和 O(n) |
| COMPOSITE | 因子 | 除法 O(log²n) |
归约证明模板
证B不可判定:①选已知不可判定的A(通常A_TM)②构造可计算f:⟨M,w⟩→B实例③证双条件:⟨M,w⟩∈A_TM⟺f(⟨M,w⟩)∈B. B可判定⇒A可判定,逆否为证.
A_TM≤_m HALT_TM
f(⟨M,w⟩)=⟨M′,w⟩. M′忽略输入,模拟M在w上:若M接受→M′停机接受;若M拒绝或loop→M′无限循环. ⟨M,w⟩∈A_TM⟺M′在w上停机.
A_TM≤_m E_TM
f(⟨M,w⟩)=⟨M′⟩. M′对输入x:若x≠w拒绝;若x=w模拟M. L(M′)={w}若M接受w,否则L(M′)=∅. ⟨M,w⟩∈A_TM⟺L(M′)≠∅∈E̅_TM.
可判定性问题总表
| 问题 | DFA | CFG | TM |
|---|
| 成员资格 | ✓(模拟|w|步) | ✓(CYK O(n³)) | ✗(A_TM不可判) |
| 空性 | ✓(BFS可达) | ✓(标记) | ✗(E_TM不可判) |
| 等价性 | ✓(对称差判空) | ✗ | ✗(EQ_TM不可判) |
| 正则性 | ✓(平凡) | ✗ | ✗(Rice) |
| 全性(=Σ*) | ✓ | ✗ | ✗(Rice) |
重点:EQ_DFA可判定,EQ_CFG和所有TM语义问题不可判定!
语言类层次(补全)
严格包含证明:{0ⁿ1ⁿ}∈CFL\Reg; A_TM∈RE\Dec; A̅_TM∈All\RE.
可判定↔可识别: L可判定⟺L和L̄都可识别. 证:并行跑M_L和M_{L̄},恰一者停机.
递归定理 (Recursion Theorem)
∀可计算t:Σ*→Σ*,∃TM R: L(R)=L(M_{t(⟨R⟩)}). TM可"获得自己的描述"并自我修改. 可用递归定理优雅地证A_TM不可判定(不显式用对角化).
递归定理应用:证A_TM不可判定—假设H判定,构造M:入w→获取自描述⟨M⟩→跑H(⟨M,w⟩)→H接受则做相反. M在w上做与H判定相反→矛盾.
补充: CFL泵引理
CFL泵引理:∃p:∀w∈L(|w|≥p)∃w=uvxyz:|vxy|≤p,|vy|>0,∀i≥0:uvⁱxyⁱz∈L. 注意:泵两部分v和y,限制|vxy|≤p(非|uv|≤p).
证{aⁿbⁿcⁿ}非CFL:w=aᵖbᵖcᵖ. vxy跨字符块或同块,分别推导矛盾. 跨块→泵后字符数不均; 同块→某字符缺失.
对角化:从Cantor到Turing
Cantor:实数不可数—假设[0,1]可列,取对角线构成不在表中的新实数. Turing:TM可数(有限描述)→语言不可数(等势R)→∃不可识别语言.
A_TM可识别(UTM模拟)但不可判定(对角线). E_TM的补可识别(∃w∈L(M)? 非确定猜w,跑M(w)→若接受则接受). E_TM本身不可识别.