字母表

形式符号的非空有限集合。

字符串

字母表 $\Sigma$ 上的一个字符串，是由 $\Sigma$ 中字符构成的一个有限序列。空串（empty string） , 常用 $\varepsilon$ 表示，不包含任何字符。字符串 $w$ 长度记为 $|w|$。

字母表上的运算

幂运算、*闭包、+闭包

语言

任何集合 $L\subseteq\Sigma*$ 是 $\Sigma$ 上的一个语言。
空语言：$\phi$不含任何字符串
仅含空字的语言：${\varepsilon}$ 含有一个字符串，即空串

语言上的运算

语言的并、连接、闭包

语言

正规语言 $\subseteq$ 上下文无关语言 $\subseteq$ 递归语言 $\subseteq$ 递归可枚举语言 | 非递归可枚举语言

上下文无关语言

上下文无关文法的四个组成要素

上下文无关文法CFG (Context-Free Grammers) 是一个四元组 $G=(V,T,P,S)$

非终结符(nonterminals)的集合 $V$：有限变量符号的集合
终结符(terminals)的集合 $T$：有限符号集，相当于字母表
产生式(productions)的集合 $P$：形如 $A\rightarrow\alpha,A\in V,\alpha\in(V\cup T)*$
开始符号(start symbol) $S$：一个特殊的非终结符

归约与推导

定义

规约：将产生式右部形式的符号串替换为产生式左部的符号
推导：将产生式左部的符号替换为产生式右部的符号串

推导关系

用 $\mathop{\Rightarrow}\limits_{G}$ 表示推导关系。若 $A\rightarrow\gamma$ 为一个产生式，则记为 $\alpha A\beta\mathop{\Rightarrow}\limits_{G}\alpha\gamma\beta$。

推导的自反传递闭包

设 $\alpha,\beta,\gamma\in(V\cup T)$，且是任意的，则归纳定义关系 $\mathop{\Rightarrow}\limits_{G}^{}$：

$\alpha\mathop{\Rightarrow}\limits_{G}^{*}\alpha$
若 $\alpha\mathop{\Rightarrow}\limits_{G}^{}\beta,\beta\mathop{\Rightarrow}\limits_{G}\gamma$，则 $\alpha\mathop{\Rightarrow}\limits_{G}^{}\gamma$

最左推导与最右推导

每次总是替换掉最左（右）边的非终结符，这样的推导称为最左（右）推导，分别用
$\mathop{\Rightarrow}\limits_{G}^{lm}$ 与 $\mathop{\Rightarrow}\limits_{G}^{rm}$ 表示新的关系。

上下文无关语言

定义 CFG $G$ 的语言为 $L(G)={w|w\in T^\wedge S\mathop{\Rightarrow}\limits_{G}^w}$，若一个语言 $L$ 是某个 CFG $G$ 的语言，则它是上下文无关语言。

语法分析树

归约过程自下而上构造了一棵树，推导过程自上而下构造了一棵树
设 CFG $G=(V,T,P,S)$，以下命题相互等价：

字符串 $w\in T^*$ 可以归约到非终结符 $A$；
A $\mathop{\Rightarrow}\limits^{*}$ w；
A $\mathop{\Rightarrow}\limits^{lm}$ w；
A $\mathop{\Rightarrow}\limits^{rm}$ w；
存在一棵根结点为 $A$ 的分析树，其果实为 $w$

二义性

文法的二义性

对于 CFG $G$，若存在一个 $w$，使得存在两棵不同的分析树，根节点均为 $S$，果实均为 $w$，则称 $G$ 是二义的。（该判定等价于存在两个不同的最左推导）

语言的二义性

若上下文无关语言 $L$ 的所有文法都是二义的，则称 $L$ 是固有二义的。

消除二义性的文法变换

算符优先级联
左结合
最近嵌套匹配：
$S\rightarrow\varepsilon|iS|iSeS$
$S\rightarrow\varepsilon|iS|iMeS,M\rightarrow\varepsilon|iMeM$

文法与语言的Chomsky分类方法

定义文法为四元组 $G=(V,T,P,S)$，Chomsky通过对产生式施加不同的限制，将文法分为四类

0型文法

产生式 $\alpha\rightarrow\beta,\alpha,\beta\in(V\cup T)^*$，$\alpha$ 中至少含有一个非终结符。能力相对于图灵机。

1型文法

产生式 $\alpha\rightarrow\beta,\alpha,\beta\in(V\cup T)^*$，要求 $|\alpha|<|\beta|$，但 $S\rightarrow\varepsilon$ 例外，且 $S$ 不能出现在产生式右部。1型文法也称为上下文有关文法(Context-Sensitive Grammer)，与它的能力相当的一种状态机是线性有界自动机。

2型文法

产生式 $A\rightarrow\beta,A\in V,\beta\in(V\cup T)^*$。2型文法也称为上下文无关文法，与它的能力相当的一种状态机是下推自动机。

3型文法

产生式形如 $A\rightarrow aB,A\rightarrow a,A,B\in V,a\in T\cup{\varepsilon}$。3型文法对应正规语言，能力等价于有限状态自动机。

正规语言

正规表达式

一种表示正规语言的代数方法

正规语言的三种运算

联合 $L\cup M$，连接 $LM$，闭包 $L^*$

正规表达式的语法

$\Sigma$ 上的正规表达式集合 $R$ 定义：

$\varepsilon,\phi\in R$
$\forall a\in\Sigma,a\in R$
$\forall E,F\in R: E+F,EF,E^*,(E)\in R$，在归纳过程中的符号不表示运算，仅表示字符串构造

正规表达式的语义

$L(\varepsilon)=\varepsilon,L(\phi)=\phi$
$L(a)=a$
$\forall E,F\in R,$
$L(E+F)=L(E)\cup L(F),$
$L(EF)=L(E)L(F),$
$L(E^*)=(L(E))*,$
$L((E))=L(E)$

正规语言

若有正则表达式 $E$ 满足 $L(E)=R$，则 $R$ 为正则语言

正则表达式的代数定律

交换律 $L(E+F)=L(F+E)$、结合律 $L((EF)G)=L(E(FG))$
零元 $\phi$、幺元 $\varepsilon$
分配律 $L(G(E+F))=L(GE+GF)$、等幂律 $L(E+E)=L(E)$

代数定律的具体化

具体化：将正规表达式中的每个变量用单个符号替换
一般化：将具体表达式中的单个符号用变量表示
举例: 对于具体符号a, 容易证明 a a* = a* a, 由此可以发
现定律 L L* = L* L, 其中 L 为变量，可以实例化为任何
语言.

有限状态自动机

确定有限状态自动机

定义

一个确定有限状态自动机 DFA (deterministic finite automata) 是一个五元组 $A=(Q,\Sigma,\delta,q_0,F)$，其中五个要素为

有限状态集 $Q$
有限输入符号集 $\Sigma$
转移函数 $\delta:Q\times\Sigma\rightarrow Q$
开始状态 $q_0\in Q$
终止状态集合 $F\subseteq Q$

扩展转移函数

$\delta’:Q\times\Sigma^*\rightarrow Q$，记 $q\in Q$，则

$\delta’(q,\varepsilon)=q$
对于 $w=xa,x\in\Sigma*,a\in\Sigma$，有 $\delta’(q,w)=\delta(\delta’(q,x),a)$

DFA的语言

定义 DFA $A$ 的语言为 $L(A)={w|w\in\Sigma^*\wedge\delta’(q_0,w)\in F}$。若对语言 $L$ 存在 DFA $A$ 使 $L=L(A)$，则 $L$ 为正规语言。

非确定有限状态自动机

$\delta:Q\times\Sigma\rightarrow 2^Q$
$\delta’(q,\varepsilon)={q}$
$\delta’(q,x)={p_1,p_2,\dots,p_k}$
$\delta’(q,w)=\Cup_{i=1}^{k}\delta(p_i,a)$
$L(A)={w|w\in\Sigma^*\wedge\delta’(q_0,w)\cap F\neq\phi}$

DFA与NFA的相互转换

DFA to NFA: trivial
NFA to DFA: 子集构造法 $Q_D={S|S\subseteq Q_N}$

带 $\varepsilon$ 转移的非确定有限自动机

$\delta:Q\times(\Sigma\cup{\varepsilon})\rightarrow 2^Q$
$\text{ECLOSE}(q)$：从 $q$ 出发沿着 $\varepsilon$ 路径能够到达的状态集合
$\delta’(q,\varepsilon)=\text{ECLOSE}(q)$
$\delta’(q,x)={p_1,p_2,\dots,p_k}$
$\Cup_{i=1}^{k}\delta(p_i,a)={r_1,\dots,r_m}$
$\delta’(q,xa)=\Cup_{j=1}^m\text{ECLOSE}(r_j)$
$O(n^32^n)$

确定有限自动机的最小化

定义 $Q$ 上的二元关系 $R$ 为，$\forall p,q\in Q$
$$pRq\iff \forall w\in\Sigma^*,\delta’(p,w)\in F\leftrightarrow \delta’(q,w)\in F$$
$\delta(r,a)=p,\delta(s,a)=q$，则 $p,q$ 可用 $w$ 区别 $\implies$ $r, s$ 可用 $aw$ 区别

填表算法

$p$ 为终态，$q$ 为非终态，则 $p,q$ 可用 $\varepsilon$ 区别
若 $p,q$ 可区别，且 $\delta(r,a)=p,\delta(s, a)=q$，则标记 $r,s$ 可区别
若 r 和 s 是不可区别的, 则对于任何输入符号, r 和 s 的后继状态之间也是不可区别的
具体步骤
删除所有从开始状态不可到达的状态及与其相关的边,
设所得到的 DFA 为 A = (Q, , , q0 , F ) ；
使用填表算法找出所有等价的状态偶对；
根据 2 的结果计算当前状态集合的划分块，每一划分
块中的状态相互之间等价，而不同划分块中的状态之
间都是可区别的. 包含状态 q 的划分块用 [q] 表示.
构造与 A 等价的 DFA $B=(Q_B,\Sigma,\delta_B,[q_0],F_B)$ , 其中
$Q_B={[q]|q\in Q},F_B={[q]|q\in F},\delta B([q],a)=[\delta(q,a)]$

正则表达式与有限自动机

正则表达式->$\varepsilon$-NFA：Tompson构造法
$\varepsilon$-NFA->正则表达式：

路径迭代法

$R_{ij}^{(k)}$：$w\in L(R_{ij}^{(k)})\iff$从 $i$ 到 $j$ 存在一条标记为 $w$ 的路径，且路径上除了首尾的所有状态编号均不大于 $k$
$$R_{ij}^{(k)}=R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^*R_{kj}^{(k-1)}$$
$O(n^34^n)$

状态消去法

$R_{11}+Q_1SP_1$
$(R+SU^T)^SU^$
$O(n^34^n)$

正规语言的性质与运算

pumping 特性

若一个字符串长度不小于状态数目，那么它所标记的路径上，必然出现重复的状态.
$w\in L,|w|\ge n$，$w$ 可分为 $w=xyz$

$y\neq \varepsilon$
$|xy|\le n$ （第一对重复的状态必发生在前 $n$ 个字符，即共经过了 $n+1$ 个状态）
$\forall k\ge 0,xy^kz\in L$

判断正规语言是否为空

求有限状态自动机，若初态可达终态，则非空

判断正规语言是否相等

求DFA，将两个DFA合并（单纯的集合一一并起来即可），然后运用填表算法，若两个初态不可区分则相等

正规语言的封闭运算

并($L\cup M$)，闭包($L^*$)，连接($LM$)，补($\bar{L}$)，交($L\cap M$)，差($L-M=L\cap\bar{M}$)，反向($L^R$)，同态($h(w)=h(a_1)h(a_2)\dots h(a_n),h:\Sigma\rightarrow T^*$)

下推自动机(PushDown Automaton)

$P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0(,F))$
$\delta:Q\times(\Sigma\cup{\varepsilon})\times\Gamma\rightarrow 2^{Q\times\Gamma*}$
栈为空时就无法转移了

当前格局

ID:$(q,w,\gamma)$
$(q,aw,X\beta)\vdash(p,w,\alpha\beta) \iff (p,\alpha)\in\delta(q,a,X)$

两种接受方式

终态接受$L(P)$，在终态停止、串为空、栈可以非空
空栈接受$N(P)$，在任意状态停止、栈与串为空
空栈->终态：增加($\varepsilon,X_0/ZX_0$)，每个节点增加($\varepsilon,X/\varepsilon$)到新状态 $P_f$
终态->空栈：增加($\varepsilon,X_0/ZX_0$)，每个终态节点增加($\varepsilon,any/\varepsilon$)到新状态 $P_f$，$P_f$加自环消除一切栈符号（只有在 $P_f$ 处才能消除 $X_0$ 符号）

确定下推自动机

DPDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$

$a\in\Sigma\cup{\varepsilon},X\in\Gamma,\delta(q,a,X)$ 至多含有一个元素
$a\in\Sigma$，若 $\delta(q,a,X)\neq\varphi$，则 $\delta(q,\varepsilon,X)=\varphi$

若 $L$ 为正规语言，则有DPDA $P,L(P)=L$
$$\delta_A(q,a)=p\iff \delta_P(q,a,Z_0)={(q,Z_0)}$$
DPDA计算能力强于DFA

前缀性质

不存在 $x,y\in L,x\neq y,x$ 是 $y$ 的前缀
若 $L$ 是空栈接受的DPDA $P$ 的语言 $L=N(P)$，当且仅当 $L$ 有前缀性质且 $L=L(P’)$,$P’$ 为DPDA
若 $L=N(P)$，P为DPDA，则 $L$ 无二义
固有二义的语言不是任何DPDA的语言，但有一些非固有二义的语言也不是任何DPDA的语言

CFG的简化与Chomsky范式

消除无用符号

有用符号：$S\mathop{\Rightarrow}\limits^{}\alpha X\beta\mathop{\Rightarrow}\limits^{}w,w\in T^*$
有用符号必定同时是生成符号与可达符号，反命题不成立
$S->AB|A,B->b$，虽然 $B$ 可达且生成，但是 $S->AB$ 实际上不可能被使用，因为 $A$ 无法被消去
步骤：

删除非生成符号及一切含有这些符号的表达式（此时可能产生新的非产生符号）
删除此时的非可达符号及一切含有这些符号的表达式

顺序不能调换，且过程结束后便没有无用符号了

消除 $\varepsilon$ 产生式

可致空符号：存在推导 $A\mathop{\Rightarrow}\limits^*\varepsilon$
对 $A\rightarrow A_1A_2\dots A_k$，若有 $m$ 个可致空符号，则改为 $2^m-1$ 个产生式

消除Unit产生式

Unit产生式：$A\rightarrow B$
Unit偶对：$A\mathop{\Rightarrow}\limits^{*}B$

计算偶对

(A,A) 是Unit偶对
(A,B)且 $B->C$是Unit产生式，则 $(A,C)$为Unit偶对

步骤：

计算所有Unit偶对集合
若 $(A,B)$ 为Unit偶对，且 $B->\alpha$ 不是Unit产生式，则在 $G_1$ 中加入产生式 $A->\alpha$
在 $G_1$ 中加入 $G$ 中所有的非Unit产生式

总步骤

消除 $\varepsilon$ 产生式
消除Unit产生式
消除无用符号
即得 $L(G_1)=L(G)-{\varepsilon}$

Chomsky范式 (CNF,Chomsky Normal Form)

产生式仅有两种形式：

A->BC,ABC均为非终结符
A->a,A为非终结符，a为终结符
不含有无用符号

任何不含 $\varepsilon$ 的非空 CFL 都有一个 CFG G 满足Chomsky范式

如果某一终结符 a 出现于某些右部长度大于 1 的产生式中，则引入一个新的非终结符，如A ，将这些产生式中的 a 替换为 A ，并增加新的产生式 A → a ；至此，右部长度大于 1 的产生式中只包含有非终结符
将右部长度大于2的产生式采用级连（cascade）
的方法转变为只包含两个非终结符；如对于产生式
$A→B_1B_2…B_k,k>2$，
引入k-2个新的非终结符$C_1,C_2,…,C_{k-2}$ ，则将
原产生式替换为以下一组产生式：
$$A→B_1C_1,C_1→B_2C_2,…,C_{k-3}→B_{k-2}C_{k-2},C_{k-2}→B_{k-1}B_k$$

上下文无关语言的性质与运算

存在一个 $n$，使得 $z\in L,|z|>n$，存在一个分解$z=uvwxy$ 使得

$vx\neq\varepsilon$
$|vwx|\le n$
$\forall k\ge 0,uv^kwx^ky\in L$

上下文无关文法是否为空的判定

可由如下步骤判定上下文无关文法表示的语言是否为空：

计算所有生成符号的集合
判定文法的开始符号是否生成符号；若是，则该文法表示的上下文无关语言非空；否则，该语言为空
算法复杂度计算生成符号集合为 O(n2) 复杂度，但若采用适当的数据结构，复杂度可降为O(n) .

判定是否含有特定字符串

步骤：

将该文法变换为符合 Chomsky 范式：
采用 CYK 算法判定该文法所产生的语言是否包含字符串 w.
CYK:
$$A\in V,A\in X_{ij}\iff A\mathop{\Rightarrow}\limits_{G}^{*}a_ia_{i+1}\dots a_j$$
$w\in L(G)\iff S\in X_{1n}$

不可判定的问题

两个上下文无关语言相交是否为空
两个上下文无关语言是否相等
给定上下文无关文法是否无二义的
给定上下文无关语言是否固有二义的
给定上下文无关语言是否等于 $\Sigma^*$

封闭运算

替换，$s:\Sigma\rightarrow L,L$ 为上下文无关语言的一个集合
并，取语言 ${0,1},s(0)=L,s(1)=M$，替换可得 $L\cup M$ 为上下文无关语言
闭包：$L^*,L^+$
连接：$LM$
同态：$w:\Sigma\rightarrow T^*$
反同态
反向
正规语言与CFL的交仍然为CFL

不封闭的运算

交、补、差

图灵机

$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$
B为空白带符
$\delta:Q\times\Gamma\rightarrow Q\times\Gamma\times{L,R}$
当前格局ID：$X_1X_2\dots X_{i-1}qX_iX_{i+1}\dots X_n$，带头在 $X_i$ 处，目前图灵机位于状态 $q$

停机指图灵机不存在下一个移动
给定图灵机 $M$，容易构造 $M’$ 使得对于 $w\in L(M)$，$M’$ 接受 $w$ 并一定停机

可以被图灵机接受的语言为递归可枚举语言

递归语言

语言 $L$ 是递归的，当且仅当存在图灵机 $M$ 使得 $L=L(M)$，且

若 $w\in L(M)$，则 $M$ 接受 $w$（到达终态且停机）
若 $w\notin L(M)$，则 $M$ 将在非终态停机

递归语言对应的问题是可判定的

带有储存区的图灵机

$Q=S\times T$，$T$ 表示数据元素集合，仍然等价于图灵机，只是状态变成了二元组。

多道图灵机

带符号可以是元组的形式，仍然等价于图灵机。

多带图灵机

有多个带头，每个带头独立移动，第 $2\sim n$ 道初始全为空带符。可用有 $2n$ 条带的带储存区的多带图灵机模拟，仍然等价于图灵机。

双栈PDA可以模拟图灵机
具有一个计数器的计数机能力不强于确定的下推自动机
具有两个及以上计数器的计数器机能力等于图灵机
具有三个计数器的计数机可以用具有两个计数器的计数机来模拟

语言的补

递归语言的补仍然为递归语
若 $L$ 与 $\bar{L}$ 均是递归可枚举的，则它们放在一起就能有停机地判断 $w$ 是否属于 $L$；递归可枚举语言的补可能是非递归可枚举语言

问题的判定

一个问题的语言如果是递归的，则它是可判定的；如果是递归可枚举的，则是半可判定的；否则是不可判定的。

字母表

字符串

字母表上的运算

语言

语言上的运算

语言

上下文无关语言

上下文无关文法的四个组成要素

归约与推导

定义

推导关系

推导的自反传递闭包

最左推导与最右推导

上下文无关语言

语法分析树

二义性

文法的二义性

语言的二义性

消除二义性的文法变换

文法与语言的Chomsky分类方法

0型文法

1型文法

2型文法

3型文法

正规语言

正规表达式

正规语言的三种运算

正规表达式的语法

正规表达式的语义

正规语言

正则表达式的代数定律

代数定律的具体化

有限状态自动机

确定有限状态自动机

定义

扩展转移函数

DFA的语言

非确定有限状态自动机

DFA与NFA的相互转换

带 $\varepsilon$ 转移的非确定有限自动机

确定有限自动机的最小化

填表算法

具体步骤

正则表达式与有限自动机

路径迭代法

状态消去法

正规语言的性质与运算

pumping 特性

判断正规语言是否为空

判断正规语言是否相等

正规语言的封闭运算

下推自动机(PushDown Automaton)

当前格局

两种接受方式

确定下推自动机

前缀性质

CFG的简化与Chomsky范式

消除无用符号

消除 $\varepsilon$ 产生式

消除Unit产生式

计算偶对

步骤：

总步骤

Chomsky范式 (CNF,Chomsky Normal Form)

上下文无关语言的性质与运算

上下文无关文法是否为空的判定

判定是否含有特定字符串

不可判定的问题

封闭运算

不封闭的运算

图灵机

递归语言

带有储存区的图灵机

多道图灵机

多带图灵机

语言的补

问题的判定