Simple Model¶
约 2919 个字 预计阅读时间 15 分钟
Regular Language & Finite Automata¶
Deterministic Finite Automata¶
有限状态机拥有一定数量的状态，状态之间通过一些特定条件进行转移。用图像表示，State Diagram 的一些表示符号如下：
一个 Deterministic Finite Automata（DFA） 由五个参数组成：
- \(K\): finite set of states
- \(\Sigma\): alphabet
- \(s\in K\): initial state
- \(F\subseteq K\): set of final states
- \(\delta\): transition function
- \(\delta: K\times \Sigma \rightarrow K\)
Final States
DFA 输入被接受的状态，若处理完一串输入后停留在 Final State，则该输入被接受；反之则被拒绝。例如，对于如下状态机，输入 aabba 会被 accepted：
设计一个 DFA，要求实现 Language \(L_1 =\{w\in \{a,b\}^* : w\text{ 没有三个连续的 b}\}\)
如果我们想要 \(L_2=\{w\in\{a,b\}^* : w\text{ 包含三个连续的 b}\}\) 怎么办?
由于 \(L_2 = \Sigma^* - L_1\)，我们只需要将 Final States \(F=\{q_0, q_1, q_2\}\) 变为 \(F=\{q_3\}\) 即可。
Configuration 是 \(K\times \Sigma^*\) 的子集，代表了一个 DFA 当前的状态，表示为 \((q,w)\)，其中：
- \(q\in K\) 为当前状态（current state）
- \(w\in \Sigma^*\) 为尚未读取的剩余输入串
我们使用符号 \(\vdash_M\) 来表示 DFA 在配置之间的转移：
此时一定有条件：
- 存在某一 Symbol \(a\in \Sigma\)
- \(w=aw'\)
- \(\delta (q,a) = q'\)
\(\vdash_M^*\) 是运算 \(\vdash_M\) 的 reflexive, transitive 的 Closure，那么 \((q, w) \;\vdash_M^*\; (q', w')\) 说明配置 \((q,w)\) 可以在有限步转移到 \((q', w')\)，并且我们此时称 \((q,w)\) yields \((q',w')\)。
这里的有限步也可以是 0，因此也有 \((q,w)\; \vdash_M^* \; (q,w)\)
此时，我们可以将上面对于 Final States 描述改为：
A string \(w\in \Sigma^*\) is said to be accepted by M iff there is a state \(q\in F\) such that \((s,w)\; \vdash_M^*\; (q,\upepsilon)\)。
所有被 DFA \(M\) 接受的 string 集合表示为 \(L(M)\)，它是被 \(M\) 接受的 Language。
Nondeterministic Finite Automata¶
NFA 不同于 DFA，它在某些状态下读到一个符号时，可能有多个去向，甚至可以不读入输入就跳转。这种不确定性让它同时尝试多条路径，只要有一条成功就接受输入。
NFA 同样是由五个参数组成，不同的是，它的转换方式由 function 变为了 relation：
- \(K\): finite set of states
- \(\Sigma\): alphabet
- \(s\in K\): initial state
- \(F\subseteq K\): set of final states
- \(\Delta\): transition relation
- \(\Delta \subseteq K\times (\Sigma \cup \{e\}) \times K\)
以下为应用 NFA 的三个例子：
两个自动机 \(M_1\),\(M_2\) 相等，当且仅当 \(L(M_1)=L (M_2)\)。我们希望证明 DFAs 和 NFAs 在能力上等价时，必须证明以下两件事：
- For each DFA, produce an NFA that accepts the same language
- For each NFA, produce an DFA that accepts the same language
其中第一点是显而易见的，对于第二点要求，给定一个 NFA，可以构造一个等价 DFA，这意味着我们需要“填补” DFA 和 NFA 之间的差异。
- Difference 1: Transition Relation
- Transition relation of DFA 一定是一个 function: \(K\times \Sigma \times K\)
- Transition relation of NFA 不一定是 function: \(K\times (\Sigma \cup \{e\}) \times K\)
- Difference 2: Domain
- The domain of transition relation of DFA is \(K\times \Sigma\)
- The domain of transition relation of NFA is \(K\times (\Sigma \cup \{e\})\)
- 即 NFA 容忍无字符输入下的状态转移
【Example】
下面我们以一个 NFA 为例：
绘制成 State Diagram 的结果如下：
为了解决以上两点 Difference，我们可以从初始状态开始思考，计算转换后的 DFA 有什么状态。我自己思考总结得到的计算方法如下：
zq 老师的 PPT 上的方法我没太理解，且绿色部分 PPT 上没有
按照定义，一个 DFA 要求每个状态对于每个输入符号都必须有且只有一个转移，否则意味着自动机在这个输入上是不确定的。
现在我们回顾一下 Language 中的闭包 EClose \(E(q)\)：
在状态机模型下，\(E(q)\) 即表示状态机 \(M\) 从状态 \(q\) 开始，在无输入的情况下能达到的所有状态的集合。
除此之外，还有一个结论是从 NFA 转换到 DFA，状态的个数可以达到指数级别的增长，例如：
这一点在我们上面画的树中也有所体现。但是实际上大部分状态都与原先的状态机无关，因此指数级只是一个上限。
【More Example】
把如下 NFA 转换成 DFA：
转换步骤仍然如上，注意最后的 Dead State 也要画出来：
Regular Language¶
以下内容大部分来自 语言、自动机与正则表达式 - 鹤翔万里的笔记本
一个 Language 被称为 regular，当且仅当它被一个自动机 \(M\) 接收。我们有定理：
- 如果 \(A\) 和 \(B\) 是正则语言，则 \(A\cup B\), \(A\circ B\), \(A^*\) 都是正则语言。
我们一般使用 \(R\) 表示正则表达式，使用 \(L(R)\) 表示该正则表达式对应的语言。一个正则表达式由如下规则定义：
- Atomic：对于 \(\emptyset\) 对应语言 \(L(\emptyset)=\emptyset\)，对于 \(a\in \Sigma\) 有 \(L(a)=\{a\}\)
- Composite：
- \(R_1 \cup R_2\) 对应语言 \(L(R_1 \cup R_2)= L(R_1) \cup L(R_2)\)
- \(R_1 R_2\) 对应语言 \(L(R_1 R_2)= L(R_1)\circ L(R_2)\)
- \(R_1^∗\) 对应语言 \(L(R_1^∗)= L(R_1)^∗\)
- 优先级：\(^*\gt \circ\gt\cup\)
- Ex. \(ab^∗ \cup b^∗a= (a(b^∗)) \cup ((b^∗)a)\)
\(R\) 和 \(L(R)\) 的对应关系
- \(\emptyset ^*\) => \(\{e\}\)
- \(a(a\cup b)^* b\) => \(\{w\in \{a,b\}^*\; :\; w \text{ starts with } a \text{ and ends with } b\}\)
- \((a\cup b)^* a (a\cup b)^* a (a \cup b)^*\) => \(\{w\in \{a,b\}^*\; : \; w \text{ contains at least two a's}\}\)
事实上，自动机和正则表达式之间是等价的，可以相互转换。要将一个 FA 转换为正则表达式，我们首先需要掌握如何通过归纳来折叠一个状态，如下是我们所使用的基本操作：
给定一个 NFA \(M\)，要化简为正则表达式 \(R\)，我们考虑为其手动新增一个初始状态和接受状态，用 e-transition 连接到原来的初始状态和接受状态，再逐一删除中间状态：
【Example】 假定有自动机 \(M\) 如下：
按照上面的逻辑，转换步骤如下：
那么最终 \(R=a^* b \left( a\cup b a^* b a^* b \right)^*\)
【More Example】
已知 \(\Sigma=\{0,1,...,9\}\)，证明 \(L=\{w: w\in \Sigma^*\text{ be the nonnegative integers divisible by 2 and 3}\}\) 是正则语言。
正则语言之间有三种运算，两个正则语言通过这三种运算的结果仍然是正则语言，因此我们可以考虑将 \(L\) 分解为可以被 2 整除的 \(L_2\) 以及可以被 3 整除的 \(L_3\) 分别证明是正则语言。
首先对于 \(L_2\)，它的特征是个位为偶数，因此表示如下，它也是通过几个正则语言运算得到的表达式：
对于 \(L_3\)，我们知道它的所有位数字加起来要是 3 的倍数，我们可以为它绘制一个 NFA：
因此 \(L_2\) 和 \(L_3\) 都是正则的，而 \(L=L_2 \cap L_3\) 自然也是正则的。
更多判断 Language 是否是正则的例子如下：
- \(L=a^*\) 是正则的，因为它被 Regular Expression 定义
- \(L=\{a^n : n\ge 0\}\) 是正则的，因为它和上面语言等价
- \(L=\{w^R: w\in L_0, \text{ and}\ L_0\text{ is regular}\}\) 是正则的
- 这里 \(^R\) 表示反转
- \(L=\{a^n: n\in Even\}\) 是正则的，因为它等价于 \(L=(aa)^*\)
- \(L=\{w\in \{a,b\}^*: w\text{ has an equal number of a's and b's}\}\) 不是正则的
- 假设 \(L\) 是正则的，那么 \(L\cap a^* b^*=\{ a^n b^n: n \ge 0\}\) 就是正则的，但是 FA 无法记忆前面有多少个 a 以确保后面出现相同数量的 b，因此矛盾
- \(L=\{a^n: n\in Prime\}\) 不是正则的
- 注意这是质数，不是奇数
- \(L=\{ww^R : w\in \{a,b\}^*\}\) 不是正则的
- \(L=\{ww: w\in \{a,b\}^*\}\) 不是正则的
- \(L=\{wcw: w\in \{a,b\}^*\}\) 不是正则的
对于任意一个非空 alphabet \(\Sigma\)，它的 String \(\Sigma^*\) 是可数无限集（Countable Infinite），而所有 Language 就是 \(\Sigma^*\) 的所有子集，其总数满足：
这意味着 Language 的总数是不可数的。
但是 Regular Language 是可数的，因为每个正则语言都可以被一个有限自动机描述，而有限自动机的集合是可数的。
Pumping Theorem¶
若 \(L\) 是一个 regular language，则存在一个常数 pump length \(p\in \mathbb{Z}^*\) 使得 \(\forall w\in L\) with \(|w|\ge p\) 可被分为 3 个部分 \(w=xyz\)，满足：
- \(\forall i \ge 0, xy^iz\in L\)
- \(|y| > 0\)
- 被 pump 的字段非空
- \(|xy| \le p\)
- \(y\) 出现在 String 的前 \(p\) 个字符内
直观上看，在 DFA 接受一个长度至少为 \(p\) 的字符串时，开始读入前 \(p\) 个字符时必然经过某一个状态两次（鸽巢原理），于是在这两个相同状态之间的读入片段 \(y\) 就是一个循环（loop），所以可以重复（或删去一次，相当于 \(i=0\)）该片段而仍保持被 DFA 接受——这就是“泵”的含义。
通常我们取 \(p\) 为某个 DFA 的状态数
泵定理是 Regular Language 的一个必要不充分条件，因此我们可以通过证明泵定理不成立来证明该语言不是一个 Regular Language。
- 假设 \(L\) 是正则的
- 那么存在泵长度 \(p\)
- 选择一个特定的字符串 \(w\in L\) 且 \(|w|\ge p\)。你的 \(w\) 可以依赖于 \(p\)（通常取与 \(p\) 相关的形式，如 \(a^p b^p\)）
- 根据泵引理，我们知道任意对满足 \(|xy|\le p, |y|>0\) 的划分 \(w=xyz\)，都应当满足 \(\forall i\ge0,\ xy^iz\in L\)
- 对任意可能的 \(y\)（满足上面的约束）构造一个 \(i\)（通常 \(i=0\) 或 \(i=2\)），使得 \(xy^iz\notin L\)。这就与泵引理结论矛盾，从而 \(L\) 非正则。
注意：第 5 步要覆盖“任意可能的 \(y\)”——也就是说你要分析所有满足 \(|xy|\le p, |y|>0\) 的情况并在每种情况下给出反例（一般通过观察 \(y\) 的组成，例如 yyy 只能由若干个 a 组成，从而改变 a 的数量会破坏语言性质）。
【Example】
证明 \(L=\{a^n b^n \mid n\ge0\}\) 非正则
- 假设 \(L\) 正则，设对应的泵长度为 \(p\)。
- 取 \(w = a^p b^p \in L\)。显然 \(|w| = 2p \ge p\)。
- 任意划分 \(w=xyz\) 满足 \(|xy|\le p, |y|>0\)。因为 \(|xy|\le p\)，\(xy\) 完全位于第一个 \(a^p\) 中，所以 \(y\) 只含
a（且至少一个a）。 - 令 \(i=0\)。则 \(xy^0z = xz\) 则比原来少了一些
a（而b个数不变），所以形状变成 \(a^{p-|y|} b^p\)，不属于 \(L\)（因为a与b的数量不同）。 - 与泵引理结论矛盾，故 \(L\) 非正则。
Example
常见的 non-regular languages 和简要证明思路 (\(p\) 是 pump length):
- \(L = \{0^n1^n\}\): 选 \(0^p1^p\)，则 \(xy^0z \notin L\)
- \(L = \{ww\}\), \(L = \{ww^R\}\): 选 \(ab^pab^p\) 和 \(b^paab^p\)，则 \(xy^0z \notin L\)
- \(L = \{0^m1^n\}\) where \(m > n\): 选 \(0^{p+1}1^p\)，则 \(xy^0z \notin L\) (\(m\ge n\) 也一样)
- \(L = \{0^m1^n\}\) where \(m < n\): 选 \(0^p1^{p+1}\)，则 \(xyyz \notin L\) (\(m\le n\) 也一样)
- 根据上面两个例子可以看出，union of 2 non-regular languages 不一定是 non-regular 的，例如 \(m > n\) 和 \(m \le n\) 的 union 是 \(0^*1^*\)
- \(L = \{0^m1^n\}\) where \(m \neq n\): 假设 regular，则 \((\{0^*1^*\} - L) \cap \{0^*1^*\} = \{0^n1^n\}\) is regular，矛盾
- \(L = \{1^n\}\) where \(n\) is prime: 选 \(1^k\) where \(k > p\) and \(k\) is prime，若 \(y = 1^s\) where \(0 < s \le p\)，则 \(\forall n \ge 0, k + (n - 1)s\) is prime。但取 \(n = k + 1\) 得到 \(k + ks = k(1 + s)\) is not prime，矛盾
- \(L \in \{0, 1\}^*\) where numbers of 0's and 1's are equal: 假设 regular，则 \(L \cup 0^*1^* = \{0^n1^n\}\) is regular，矛盾
Context-free Languages & Pushdown Automata¶
Context-free Language¶
在形式化定义上，一个 Context-Free Grammar, CFG 由四个部分组成 \(G=(V, \Sigma, R, S)\)：
- \(V\)： Alphabet
- \(\Sigma \subseteq V\): The set of terminal symbols
- \(V-\Sigma\): the set of non-terminals
- 非终结符一定是非空集合，因为起码包含 \(S\)
- 而终结符可以为空集 \(\emptyset\)
- \(S\in V-\Sigma\): The start symbol
- \(R\): The set of rules
- \(R\subseteq (V-\Sigma) \times V^*\)
- 是可数集合，形式为 \(A\rightarrow \alpha\)，其中 \(A\in V-\Sigma,\; \alpha \in V^*\)
CFG 的上下文无关体现在 \(R\) 中的 rules 左侧只能是单个非终结符。
终结符的意义在于，在根据定义的规则推导过程中，它们不能被替换；当推导到只剩下终结符时，表示生成完成
对应的，一个语言 \(L\) 是 Context-Free Language（CFL） 当且仅当存在一个 CFG \(G\) 使得 \(L=L(G)\)，即可以被 CFG 生成。
Language \(L\) is CFL iff \(L=L(G)\)
这个表述是错的，还要说明 \(G\) 是一个 CFG 😂
Language \(L\) is CFL iff it is accepted by a CFG
这个表述也是错的，正确表述为：Language \(L\) is CFL iff it is generated by a CFG
Regular Language 是 CFL 的子集，即 All Regular Languages are CFL
| 主题 | 正规语言（Regular Language） | 上下文无关语言（Context-Free Language, CFL） |
|---|---|---|
| 生成工具（Generation Device） | Regular Expression（正规表达式） | Context-Free Grammar（上下文无关文法） |
| 识别工具（Recognition Device） | Finite Automata（有限自动机，FA） | Pushdown Automata（下推自动机，PDA） |
| 等价关系（Equivalence） | FA ⇔ Regular Expression | PDA ⇔ Context-Free Grammar |
【Example】
- 终结符为 \(\{a,b\}\)
- 开始符为 \(S\)
- 产生式集合为 \(\{S\rightarrow aSb, S\rightarrow e\}\)
- 或者表示为 \(\{(S,aSb),\; (S,e)\}\) 或 \(\{S\rightarrow aSb\; |\; e\}\)
这里的开始符 \(S\) 只是生成规则中的“变量”，最终要在推导生成中被替换为结束符
【More Example】
即证明回文字符串是上下文无关的，我们构造 CFG：
- \(S\rightarrow e,\; S\rightarrow a,\; S\rightarrow b\)
- \(S\rightarrow aSa,\; S\rightarrow bSb\)
- 可以简写为 \(S\rightarrow e \;|\; a \;|\; b \;|\; aSa \;|\; bSb\)
Parse Tree¶
CFG 的推导可以表示为一个 parse tree，该树的叶节点为 terminal symbols，根节点为 start symbol，其余节点为 alphabet \(V\) 中的元素。
例如，对于 \(a^nb ^n\)，可以绘制如下 parse tree 表示 \(a^4 b^r \in a^n b^n\)：
我们对能推理出相同的 parse tree 的推导称为是 similar 的，它也可以被定义为 precedes 关于 reflexive, symmetric, transitive 的闭包。
\(D\) precedes \(D'\; \Leftrightarrow \exists \; 1 \le k \le n\):
- For all \(i\ne k\), we have \(x_i =x_i'\)
- \(x_{k-1} = x_{k-1}' = uAvBw\), where \(u,v,w\in V^*\), and \(A,B\in V-\Sigma\)
- \(x_k=uyvBw\), where \(A\rightarrow y \in R\)
- \(x_k' = uAvzw\), where \(B\rightarrow z \in R\)
- \(x_{k+1}= x_{k+1}' = uyvzw\)
一个 ambiguous 的 grammar 存在一些 String 可以由不同的 parse tree 推导。
Pushdown Automata¶
下推自动机（Pushdown Automata, PDA）是一个带栈结构的 NFA，它可以使用栈做一些记忆功能。
在形式化定义上，PDA 由六个部分组成 \(P=(K,\Sigma, \Gamma, \Delta, s, F)\)：
- \(\Gamma\): stack alphabet
- 栈中能出现的符号集合
- \(\Delta\): transition relation
- \(\Delta \subseteq \left(K\times (\Sigma \cup \{e\})\times \Gamma^* \right)\times \left(K\times \Gamma^* \right)\)
- 对于 NFA 的 \(\left(K\times (\Sigma \cup \{e\}) \right)\times K\)，在转移前后都增加了栈相关字符串
- 前一个 \(\Gamma^*\) 是栈顶字符串，匹配后 pop 出来
- 后一个 \(\Gamma^*\) 是转移后要 push 进去的字符串
最后判断能否接受一个 String \(w\) 要求不仅状态位于 Final State，还要 Stack 为空。用 \(\vdash\) 表示，则记为：
相应的，能被 PDA \(M\) 接受的语言记为：
在表示上，我们在状态转移的箭头上新增一个项，表示我们从栈中 pop/push 了什么符号，例如 \(\left((p,u,\beta), (q,\gamma)\right)\in \Delta\)：
我们一般所说的 PDA 都是非确定性的，允许读取一个符号后（再根据栈的状态）做不同转移，也允许做 e-transition；而确定性的 PDA 并不与 CFL 等价，此处不再证明，请直接记住这个结论。
例如，对于 \(L(M)=\{ww^R\; :\; w\in \{a,b\}^*\}\)，它的 diagram 如下：
Example
Is c necessary?
\(c\) 被用作栈底标志，可以简化 PDA 的设计，但并不是必要的。
事实上，对于 \(L(G)=\{wcw^R\; : \; w\in \{a,b\}^*\}\) 这种拥有形如 \(R=\{S\rightarrow aSa\;|\; bSb\;|\;c\}\) 的规则的 CFG，可以分如下三步构造 PDA 的转移方程：
对字符串 abbcbba 按照如上转移方程进行推导
Pumping Theorem for CFL¶
若 \(L\) 是一个 Context-Free Language，则存在一个常数 pump length \(p\in \mathbb{Z}^*\) 使得 \(\forall w\in L\) with \(|w|\ge p\) 可被分为 5 个部分 \(w=uvxyz\)，满足：
- \(\forall i \ge 0, uv^i xy^iz\in L\)
- \(|v|+|y| > 0\)
- 被 pump 的字段非空
- \(|vxy| \le p\)
- \(y\) 出现在 String 的前 \(p\) 个字符内
泵定理是 Context-Free Language 的一个必要不充分条件，因此我们可以通过证明泵定理不成立来证明该语言不是一个 Context-Free Language。