前言

这是形式语言与自动机的课程笔记，推荐读物是:

• Michael Sisper. Introduction to the Theory of Computation.
• Peter Linz. An Introduction to Formal Languages and Automata.
• Arindama Singh. Elements of Computation Theory.

有穷自动机FA & 正则语言REG

确定性有穷自动机PDA

确定性有穷自动机DFA可以用五元组、状态转移框图、状态转移表等形式表示

1
2
3
4
5
6
7
8

DFA = (Q, Σ, δ, q0, F)，其中: 
    Q          状态集
    Σ          输入字母表
    δ          转移函数 δ = Q × Σ -> Q, 可扩展为 δ* = Q × Σ* -> Q
    q0 ∈ Q    初始状态
    F ⊆ Q     终止状态集

一步转移: δ(q, a) = p

DFA A所识别的语言为L(A) = { w | δ*(q0, w)∈F, w∈Σ* }

正则语言REG

1
2
3
4

正则语言是左线性或者右线性语言，其乔姆斯基范式的文法中，只有形如这两条的规则: 
  A -> xB  或  A -> Bx
  A -> x       A -> x
其中A和B是非终结符，x是终结符

性质

泵引理: 对∀L∈RE，∃n(即对应的某DFA的状态数)，使得对于∀w∈L，若|w|>=n，则可分解为w=xyz且满足

1. |xy| <= n
2. |y| > 0
3. ∀i >= 0, w’ = x(y^i)z ∈ L

可判定性:

• Areg: 成员资格，直接运行A(w)即可
• Ereg: 空语言，DFS标记所有可达状态、断言至少有一个在终态集中
• Ireg: 无穷语言，移除不可达状态和不可终止状态后、断言残余图有环
• EQreg: 相等语言，构造乘积自动机FA A’，设置其接受态为恰好被原FA的其中之一接受(对称差的意味)，断言A’为空
• Creg: 包含于关系()，构造乘积自动机FA A’，设置其接受态为第一个接受、第二个不接受，断言A’为空(即L1-L2=∅)

封闭性:

• 并: 修改文法为S’->S1|S2 或 修改正则式为S1|S2
• 连接: 修改文法为S’->S1S2 或 修改正则式为S1S2
• 克林闭包: 修改文法为S’->SS’|ε 或 修改正则式为S*
• 交: 构造乘积自动机FA A’，设置其接受态为两个都接受
• 差: 构造乘积自动机FA A’，设置其接受态为第一个接受、第二个不接受
• 补: 由差的封闭性知Σ*-L亦是正则
• 逆: 修改正则式为rev(R)，递归化简
• 同态: 修改正则式为map(S, x -> h(x))，把单个符号变成多个符号
• 逆同态: 考虑自动机，在读入每个符号后、使用逆同态函数h’将其解码为多个符号，其余照旧

正则表达式Regex

1
2
3
4

递归定义: 
  1. 若 a 在字母表中，则 a 是Regex
  2. 若 r1 和 r2 是Regex，则 r1|r2 和 r1*r2 是Regex
  3. 若 r 是Regex，则 r* 是Regex

Regex E所定义的语言为L(E)，同样地，

1
2
3
4
5
6

递归定义: 
  1. L(∅) = ∅, L(ε) = {ε}
  2. 若 a 在字母表中，则 L(a) = {a}
  3. 若 l1 和 l2 是RE，则L(l1 + l2) = L(l1) ∪ L(l2)
  4. 若 l1 和 l2 是RE，则L(l1 * l2) = L(l1) * L(l2)
  5. 若 l 是RE，则L(l*) = (L(l))*

等价性与转换

与DFA的计算能力/表达能力的模型:

• DFA -> Regex: k-path矩阵动规，每次消去第k个状态Rij[k] = Rij[k-1] + Rik[k-1](Rkk[k-1])*Rkj[k-1]，Rij[k]表示从i到j最多绕过前k个节点所成语言对应的Regex
• Regex -> REG: 观察法构造其REG文法
• REG -> ε-NFA: 依定义构造状态转移框图，注意盲目省略ε可能会出错
• ε-NFA -> NFA: 计算ε闭包，将ε折叠到下一个输入字符上去，δn(q, a) = ∪[p∈εCL(q)]δe(p, a)
• NFA -> DFA: 子集构造法，将下一步可达状态集映射为DFA中的单个状态

DFA最小化

不可区分状态消去法: 画出转移表，首先标记是任何一个终态和任何一个非终态是可区分的，然后根据转移函数逆向推理，对于任意输入字母a、它是否能分区两个态: 若A和B可区分，又有δ(C,a)=A, δ(D,a)=B，则C和D可区分。反复标记直到收敛，将不可区分的状态合并为一，然后消除(可能会产生的)不可达状态；重复多次过程直到所有状态都可区分

两次反向法: 将所有边反转得到NFA后将其化为DFA、该DFA将接受rev(L)，因此再重复上述操作一次即可

下推自动机PDA & 上下文无关语言CFL

确定性下推自动机DPDA

确定性下推自动机DPDA可以用七元组、状态转移框图、迁移函数表等形式表示

1
2
3
4
5
6
7
8
9
10
11

DPDA = (Q, Σ, Γ, δ, q0, Z0, F)，其中: 
    Q          状态集
    Σ          输入字母表
    Γ          栈符号集
    δ          转移函数 δ = Q × Σ × Γ -> Q, 可扩展为 δ* = Q × Σ* × Γ -> Q
    q0 ∈ Q    初始状态
    Z0 ∈ Γ    初始栈顶符号
    F ⊆ Q     终止状态集

一步转移: δ(q, a, Z) = (p, Y)  // 若为NPDA则形如 {(p, Y), (r, X), ..}
快照记述法: (q, aw, Xα) |- (p, w, Yα)，即使用了转移 δ(q, a, X) = (p, Y)；亦可扩展为多步 |-*

DPDA P所识别的语言有两种定义方式:

• 终止态接受: L(P) = { w | (q0, w, Z0) |-* (p, ε, Y), p∈F, Y∈Γ, w∈Σ* }
• 空栈接受: N(P) = { w | (q0, w, Z0) |-* (p, ε, ε), p∈Q, w∈Σ* }

它们不一定相同，但可以构造另一个DPDA P'使得L(P) = N(P')，反之亦然，因此语言的表达能力相同:

• L(P) -> N(P'): P'使用新的初始栈顶符号X0、使用新状态init以开始、新状态pop以清栈，设置初始转移δ(init, ε, X0) = (q0, Z0X0)，然后修改P的转移函数，对所有δ(f, ε, X), f∈F, X∈Q设置转移目标为(pop, ε)，然后pop态不停地退栈δ(pop, ε, X) = (pop, ε), X∈Q。正确性直觉: 只有pop态才能清空栈底的X0！
• N(P) -> L(P'): P'使用新的初始栈顶符号X0、使用新状态init以开始、新状态halt以结束，设置初始转移δ(init, ε, X0) = (q0, Z0X0)，对所有δ(q, ε, X0), q∈Q设置转移目标为(halt, ε)。正确性直觉: 任何空栈态，就会被移入终态而接受(哨兵X0好像不必要？)

不确定性下推自动机NPDA

从表达能力上，我们有:

1
2
3
4

                  > DPDA(N(P)) x
NPDA > DPDA(L(P))       >        REG

*即N(P)弱于L(P)，但N(P)与RE不可比较

NPDA确实比DPDA计算能力强: DPDA无法判定语言L = { w\*rev(w) | w ∈ Σ* }，但是NPDA可以”猜测/穷举”正确的折半点，即NPDA才能定义标准的CFL，如上例L的上下文无关文法为S->0S0|1S1|ε

上下文无关语言CFL

1
2
3
4
5
6
7
8

上下文无关语言的文法规则必须满足: 
  1. 左部总是一个非终结符
  2. 右部是若干个终结符和非终结符

例如: 
  A -> BaCb|c
  B -> cA|CCa
  C -> B|b

文法推导: 从文法开始符号不断应用规则最终得到全部都是终止符的句子的过程序列；特别地，最左推导指总是替换最左边的非终止符

约简与范式化

五个步骤:

1. 消除空产生式: 从形如A->ε的产生式逆推所有可空的非终止符、在所有地方展开它们，然后从语言中消去S->ε
2. 消除单元产生式: 若A ->* B且B ->* α的每一步都不再是单元推导，则折叠A ->* B为一步、并消去冗余符号B
3. 消除无用变量: 从只含终止符的产生式逆推所有有用的变量，消除无用的符号
4. 消除不可达变量: 从开始符号S顺推所有可达的变量，消除不可达的符号
5. 乔姆斯基范式化: 将所有产生式拆解成A->a或A->BC的形式

性质

泵引理: 对∀L∈CFL，∃n(即对应的某文法产生式个数数)，使得对于∀w∈L，若|w|>=n，则可分解为w=uvwxy且满足

1. |vwx| <= n
2. |vx| > 0
3. ∀i >= 0, w’ = u(v^i)w(x^i)y ∈ L

可判定性:

• Acfl: 成员资格，如果有PDA、直接运行P(w)即可，如果有文法、则使用CYK算法
• Ecfl: 空语言，检查文法开始符号的有用性
• Icfl: 无穷语言，检查文法非终结符依赖关系成环
• *EQcfl、DISJOINTcfl等不可判定

封闭性:

• 并: 修改文法为S’->S1|S2
• 连接: 修改文法为S’->S1S2
• 克林闭包: 修改文法为S’->SS’|ε
• 逆: 修改每个文法的右端为其逆
• 同态: 修改每个文法的右端为map(right_part, x -> h(x))，把单个符号变成多个符号
• 逆同态: 考虑自动机，在读入每个符号后、使用逆同态函数h’将其解码为多个符号，其余照旧
• *交、差、补不封闭
• *CFL与RE的交是CFL: 自动机部分变成乘积自动机、栈还是单栈，组合起来还是PDA

等价性与转换

• DFA -> CFL: 画出状态转移框图，考虑将”从p到q的迁移会消去栈顶的X”记作非终止符[pXq]，则对δ(p, a, X) = (q, ε)产生[pXq] -> a，对δ(p, a, X) = (r, Y)产生一组[pXq] -> a[rYq], q∈Q，对δ(p, a, X) = (r, YZ)产生一组[pXq] -> a[rYs][sZq], s,q∈Q，增加一组处理开始符号S -> [q0Z0q], q∈Q，然后重命名、化简、消去不可达
• CFL -> DFA: 只需一个状态q、采用空栈接受，考虑文法的乔姆斯基范式，对A->a产生转移δ(q, a, X) = (q, X), X∈Γ，对A->BC产生转移δ(q, ε, A) = (q, BC)；若是左线性文法则更简单，直接看吃什么压什么即可

图灵机TM & 递归可枚举语言RE & 递归语言R

确定性图灵机DTM

确定性图灵机DTM可以用七元组、状态转移框图、迁移函数表等形式表示

1
2
3
4
5
6
7
8
9
10
11

DTM = (Q, Σ, Γ, δ, q0, B, F)，其中: 
    Q          状态集
    Σ          输入字母表
    Γ          纸带符号集
    δ          转移函数 δ = Q × Γ -> Γ × D × Q, 可扩展为 δ* = Q × Γ* -> Γ × D × Q
    q0 ∈ Q    初始状态
    B ∈ Γ     空白符号
    F ⊆ Q     终止状态集

一步转移: δ(q, 1) = (p, 0, R)
快照记述法: q11 |- 1q1 |- 11q |- 11p |- 1r0 |- r00 |- p100   (二进制加1)

DTM M所识别的语言有两种定义方式:

• 终止态接受: L(M) = { w | q0w |-* p, p∈F, w∈Σ* }
• 停机接受(转移函数未定义): H(M) = { w | q0w |-* p, p∈Q且δ(p, ?)未定义, w∈Σ* }

它们不一定相同，但可以构造另一个DTM M'使得L(M) = H(M')，反之亦然，因此语言的表达能力相同:

• L(M) -> H(M'): 若原转移函数是个偏函数，则补全所有未定义分支使其进入一个循环状态(例如一直往右跑、从而会不停机)，尔后对于M所有的终态、删除其所有转移
• H(M) -> L(M'): 引入一个终止态如halt，将M所有无转移的状态、在所有合法输入上一步转移到这个终态

定义的健壮性

• 多磁道可以被单带模拟: 状态空间编码为每个磁道状态空间的笛卡儿积，逐磁道处理
• 双端无限纸带可以被单端无限纸带模拟: 对折一下就行了
• 多带可以被单带模拟: 模拟双磁道，记录每个带子磁头位置，逐带处理
• NTM可以被DTM模拟: 模拟双带，以BFS的方式搜索解空间；效率下降一个多项式

递归可枚举语言RE & 递归语言R

进一步地我们可以定义两类语言:

• 递归可枚举语言RE: 仅满足L(M)或H(M)其一的条件
• 递归语言R/可判定语言/算法: 同时满足L(M)和H(M)的条件

性质

可判定性:

• RE: 根据莱斯定理，都不可判定
• R: 可以判定算法

封闭性:

• RE/R都具有
  • 并: 并行运行两个TM，结果取or
  • 交: 并行运行两个TM，结果取and
  • 连接: 用NTM去猜测输入串的二分点，在前半段上模拟M1、后半段上模拟M2，断言都接受
  • 克林闭包: 用NTM去猜测所有可能的切分情况，逐个尝试、断言都接受
  • 逆: 先将输入取逆，然后断言接受
  • 逆同态: 使用逆同态函数h’将输入解码，然后断言接受
• RE特有
  • 同态: 用NTM取猜测解码方式
• R特有
  • 差: 并行运行，断言第一个接受、第二个拒绝
  • 补: 运行结果取反

可判定性 & 计算复杂性

全语言谱系

1
2

REG < CFL < R < RE < Σ*
               coRE

真包含的证据:

• Σ*真包含RE(存在不是RE的语言): RE语言即图灵可识别语言，因此RE语言的数量等于图灵机数量，TM是可数的(自然数编码)、而全体语言是不可数的(对角线方法、语言视作句子的特征向量)；考虑coHALT∈coRE而∉RE
  • 因有coHALT∈coRE、若再有coHALT∈RE则coHALT∈R即可计算，从而取反得HALT可计算
• RE真包含R(存在不可判定的语言): 停机问题HALT、NC函数(对角线方法)
• R真包含CFL: 考虑PDA无法计数三个变量 L = { (a^n)(b^n)(c^n) | n>=0 }
• CFL真包含REG: 考虑FA无法计数 L = { (a^n)(b^n) | n>=0 }

可计算谱系 & 复杂性

1

[REG] < [CFL] < L < NL = coNL < P <= NP < BPP < PSPACE = NPSPACE = IP < EXP < [R = RE ∩ coRE]

类P: DTM多项式时间可计算

P问题: PATH(Floyd算法)、RELPRIME(欧几里得算法)、Acfl(CYK算法)

类NP: NTM多项式时间可计算，或者DTM多项式时间可验证

NP问题: HAMPATH、CLIQUE、3SAT

卡普规约

若存在多项式时间可计算函数f使得任意x∈Σ*都有，若x∈L则f(x)∈P、若x∉L则f(x)∉P，则称L可多项式时间规约到P并记作L <=p P

例子: HALT <=p Atm、Etm <=p Atm (Atm是图灵机接收串问题，Etm是图灵机上的空语言问题)

NP完全性: L在NP中，NP中的任何语言都可以卡普规约到L

NP完全问题: SAT、3SAT(Cook-Levin定理)

丘奇-图灵论题

弱: 任何物理计算机能做的计算都能被图灵机计算

强: 任何物理计算机在T(n)时间内能做的计算都能被图灵机在T(n)^O(1)时间内计算，即效率多项式下降

迁移系统TS

1
2
3
4
5
6
7
8
9
10

TS = (S, S0, T, α, β, λ)，其中: 
    S          状态集
    S0 ⊆ S    初始状态集
    T          转移规则集 t: s -> d, 其中t∈T, s,d∈S
    α          取源函数   α(t) = s
    β          取目的函数 β(t) = d
    λ          取动机函数 λ(t) = l

T的规则可能有相同的源和目的(但动机不同)
若S和T都是有穷集，则称该TS是有限的

路径: 对t∈T, 亦即α(t)=s, β(t)=d称s->d，将其递归扩展为s->>d，则称s到d存在路劲

• T+: 所有有限长路径之集
• Tω: 所有无限长路径之集

迹: 路径上的标志/动机的连成列表

状态的属性:

• 可达态: s∈S, s0∈S0且s0->>s(经多步转移)
• 终止态: s没有出边
• 死锁态: s同时可达且终止

与其对应的状态机可以视为扩展的、泛化的确定性有穷自动机，可用迁移图表示: 圆形节点代表状态、有向边表示迁移(边上的标记表示动机)，实例:

TS等价的判定:

• 强同态等价: 两个TS的所有状态、迁移都可由某个双射函数关联；直觉上即结构完全一致、只是命名不同
• 弱同态等价: 两个TS从任意状态出发的可达状态集可由某个双射函数关联；直觉上即将强同态约束到所有可达状态上
• 双向模拟等价: 两个TS从任意状态集出发的可达状态集可由某个双射函数关联；直觉上即前者的一个状态集等价于后者的另一个状态集、功能性地可相互实现

计算树逻辑CTL

应用: 时序电路、并发互斥协议；例，一个单输入x、单变量r、单输出y电路:

• y = not (x xor r[k])
• r[k+1] = x or r[k]

计算树上用于节点描述的状态公式SF(state formula): 就是普通的谓词公式

计算树上用于时间性描述的路径公式PF(path formula):

• 量词算子: A(对于所有计算路径都有)、E(存在某个计算路径会使得)
• 时间算子: X(下一步就会p)、F(最终会p)、G(总是会p)、U(直到q之前都是p)、R(p一旦出现就会持续q)

一些化简公式({EX, EG, EU}是语义完备的):

• AX.f = !EX.!f
• EF.f = E[(True)Uf]
• AG.f = !EF.!f
• AF.f = !EG.!f
• A[fUg] = !E[!gU(!f^!g)]^!EG.!g
• A[fRg] = !E[!fU!g]
• E[fRg] = !A[!fU!g]

例子(p,q是命题/陈述/事件):

• AG.p: 在任何情况下，p总是会一直发生
• EF.p: 在某种情况下p有可能发生，且也不保证之后会持续发生
• AF.EG.p: 在任何情况下最终都会如此，即在某种情况下p会发生且永久持续
• EG.AF.p: 在某种情况下总是会发生这样的事，即在任何情况下p最终都会发生
• A[pUq]: 总是如此，即p会持续发生、但直到q发生(就不再保证p还会发生了)
• E[(EX.p)U(AG.q)]: 可能如此，即某种情况下在下一步就会发生p、但直到在任何情况下总是发生q的时候(就不保证前者了)

FP可以用来描述系统的性质:

• Safety: AG.p // always satisfy some certain constraint p, bad things not happen
• Liveness: AF.p // something good would finally happen
• Fairness: AG.AF.p // something is successful infinitely often

Petri网PN

PetriNet设计为离散并行系统的数学表示，是动态的、异步的、非确定性的
受此启发的其他模型: 检查系统死锁的资源配置图、UML数据流图、UML活动图

1
2
3
4
5
6
7
8

C = (P, T, I, O)，其中: 
    P          场地(理解为状态、局域性的)，圆圈表示，可以放令牌(理解为资源)
    T          转移(理解为动作/异步事件)，竖条表示
    I          输入 I: T -> P^|P|
    O          输出 O: T -> P^|P|

*其状态图转移是个关于场地集与转移集的二分图，有向边只能在P和T之间连接
 若一个转移的所有前驱场地拥有足够的令牌，则称该转移是enabled，此时它可以fire从而发生资源转化

行为属性:

• 可达性: 从M0出发可达Mn，若存在一系列的firings
• 有界性: 任何从M0出发可达的场地在任何时候拥有的资源都是有限的
• 安全性: 即1-有界
• 活性: 亦即无死锁，好事最终会发生
• 可逆性: 若Mn到M0可达、且M0到Mn可达
• 可持久化: 对任意两个enabled转移、fire其中一个不会使得另一个变得disabled(出现了资源抢夺: A+B->D,A+C->E)
• 公平性: 有界公平性(允许其中一个转移fire而其他都不fire的次数是有界的)，无条件公平性(在总的fire序列中，统计上每个转移都可以发射无限次)

分析方法: 覆盖树(类似于计算树，从给定初始状态M0出发，建树以描述之后的系统演化谱系)

常见扩展: 着色PN(token上可以标写值), 连续PN(token数量是连续值)，边抑制(Inhibitor Arcs, enable一个转移、若其前件场地没有令牌)、时间化TPN（参考下一节的TA，给每个转移的fire时机规定一个时间段约束[s,e])

时间自动机TA

设计思想: 给DFA加上若干个离散/连续的时钟，这些时钟可以用于约束状态的停留时间、限制两个状态间迁移的时间差

1
2
3
4
5
6
7
8
9
10

A = (L, X, I0, E)，其中: 
    L          位置集
    X          时钟集，时钟是全局的
    I0 ∈ L    初始位置
    E          边集 e ∈ L × C(X) × 2^X × L

时钟约束函数C(X)规定了约束条件的语法为 `C ::= x <=k | x < k | C and C | not C` 总之就是简单的二元比较，应用中为了方便可以简写 `== | !=` 等等

边的完整四元组 e = (src_loc, clk_cond, clk_reset, dest_loc)
TA的语义是一个`TS Sa = (S, s0, ->)`

时钟操作(v是时钟集Y的估值函数v: X -> R+):

• 重置: v[Y:=0](x) = if x ∈Y then 0 else x
• 时间流逝: (v + d)(x) = v(x) + d，将时钟x拨动d个tick
• 约束断言: v |= c 表示v集满足约束方程组c

时钟约束的语义:

• 迁移(边)上的时钟:
  • x > 5: 满足该条件才能跳转
  • y := 0: 把时钟y重置
• 状态(点)上的时钟:
  • x <= 6: 不满足该条件时就必须立刻迁移