语言、自动机与正则表达式 ¶

前言 ¶

• 问题分类
  • 优化问题（Optimization Problem）如最小生成树
  • 搜索问题（Search Problem）如找一棵权重最大为 k 的生成树
  • 决策问题（Decision Problem）如判断是否存在一棵权重最大为 k 的生成树
  • 计数问题（Counting Problem）
• 决策问题最简单
  • 对于一个问题有 yes-instance 和 no-instance
  • 问题可以转化为 Given a string \(w\), whether \(w\in \{\text{encoding of yes-instance}\}\)
  • \(\{\text{encoding of yes-instance}\}\) 就是一个语言（Language）

语言定义 ¶

• 字母表 Alphabet: finite set of symbols
  • \(\Sigma = \{a, b, c\}\)、\(\Sigma = \{0, 1\}\)、\(\Sigma = \{\ \}\)
• 字符串 String over \(\Sigma\): finite sequence of symbols from \(\Sigma\)
  • \(w = 010101\)，\(w = e\)（或 \(\epsilon\)）是空串
  • \(|w|\) 表示字符串长度，\(|e| = 0\)
  • \(\Sigma^i\): set of all strings of length \(i\) over \(\Sigma\)
  • \(\Sigma^* = \bigcup_{i\geq 0} \Sigma^i\)（\(\Sigma\) 上所有字符串），\(\Sigma^+ = \bigcup_{i\geq 1} \Sigma^i\)
  • 字符串操作
    • 拼接（concatenation）：\(w_1w_2\)，\(|w_1w_2| = |w_1| + |w_2|\)
    • 反转（reversal）：\(w^R\)，\(|w^R| = |w|\)
    • 重复（exponentiation）：\(w^i = \underbrace{ww\cdots w}_{i\ times}\)，\(|w^i| = i|w|\)
• 语言 Language over \(\Sigma\): any subset of \(\Sigma^*\)

自动机 ¶

自动机（finite automata）有两种：

• Deterministic Finite Automata (DFA)：确定性有限自动机，每一步的转移都是确定的
• Non-deterministic Finite Automata (NFA)：非确定性有限自动机，每一步的转移可以有多种选择

DFA¶

• 如上图就是一个 DFA，\(q_0\) 是初始状态，双圈 \(q_1\) 是接受状态，箭头上的字母是转移条件
• 一个 NFA 定义为一个五元组 \(M = (K, \Sigma, \delta, s, F)\)
  • \(K\)：状态集合
  • \(\Sigma\)：字母表
  • \(\delta\)：转移函数，\(\delta\colon K\times \Sigma \to K\)
  • \(s\)：初始状态
  • \(F\)：接受状态集合
• 执行逻辑：输入一个字符串，从初始状态，每次取出第一个字符，根据当前状态和字符查找转移函数，得到下一个状态，直到字符串为空
• configuation：\(C = (q, w)\)，表示当前状态 \(q\) 和剩余字符串 \(w\)
• yields
  • yields in one step：可一步转移到
    • 记为 \((q, w)\vdash_M (q', w')\)，if \(w=aw'\) for some \(a\in\Sigma\) and \(\delta(q, a) = q'\)
  • yields：可转移到
    • 记为 \((q, w)\vdash_M^* (q', w')\)，if \((q, w)\vdash_M (q_1, w_1)\vdash_M \cdots \vdash_M (q', w')\)
• 自动机接受字符串
  • \(M\) accepts \(w\in\Sigma^*\), if \((s, w)\vdash_M^* (q, e)\) for some \(q\in F\)
  • 即可以从初始状态 \(s\) 通过一系列转移得到接受状态 \(q\)，且剩余字符串为空
• 自动机对应的语言（Language of \(M\)）
  • \(L(M) = \{w\in\Sigma^*: M\text{ accepts }w\}\)
  • 即所有能被自动机接受的字符串
• 自动机接受的语言
  • \(M\) accepts \(L\) if \(M\) accepts every string in \(L\) and rejects every string not in \(L\)
  • \(M\) accepts \(L(M)\)

NFA¶

• 如上图是一个 NFA，和 DFA 有以下两个区别：
  • 一个状态同一条件可以有多个转移方案
  • 可以有 \(e\)-transition，即不消耗字符的转移
• 同样定义为五元组 \(M = (K, \Sigma, \Delta, s, F)\)
  • 和 DFA 区别只在 \(\Delta\)，是一个比函数更一般的关系（relation）
  • \(\Delta\)：转移关系，\(\Delta\subseteq K\times (\Sigma\cup\{e\})\times K\)
• 对于一个输入，NFA 可以有多种路线，但只要有一种路线能够接受，就认为 NFA 接受该输入
  • 一种理解方式：NFA 可以猜测该往哪里转移，且总能猜对

NFA 与 DFA ¶

• NFA 虽然看起来比 DFA 强大，但其二者实际上是等价的
  • \(\forall\) NFA \(M\)，\(\exists\) DFA \(M'\)，s.t. \(L(M) = L(M')\)
  • \(\forall\) DFA \(M\)，\(\exists\) NFA \(M'\)，s.t. \(L(M) = L(M')\)
• NFA 转 DFA 主要思路
  • NFA 接收一个字符，会有多个转移方案，所有可达的下一状态合在一起的集合构成 DFA 的一个状态
  • 即 DFA 的状态是 NFA 的状态的幂集，结束状态是包含 NFA 的结束状态的 DFA 状态
  • \(e\)-transition 也要考虑，且不算在字符数里
• NFA \(M=(K, \Sigma, \Delta, s, F)\) 转为 DFA \(M'=(K', \Sigma, \delta, s', F')\)
  • \(K' = 2^K = \{Q: Q\subseteq K\}\)
  • \(F' = \{Q\in K': Q\cap F\neq \emptyset\}\)
  • \(s' = E(s)\)
    • 定义 \(\forall q\in K, E(q) = \{p\in K: (q, e)\vdash_M^* (p, e)\}\)
    • 即 \(E(q)\) 是 \(q\) 可以通过 \(e\)-transition 到达的状态集合
  • \(\delta\): \(\forall Q\in K', \forall a\in\Sigma\)

正则语言 ¶

• A language is regular if it is accepted by some FA
  • 有自动机可以接受的语言是正则的
• Regular Operations
  • Union: \(A\cup B = \{w: w\in A\text{ or }w\in B\}\)
  • Concatenation: \(A\circ B = \{ab: a\in A\text{ and }b\in B\}\)
  • Star: \(A^* = \{w_1w_2\cdots w_k: k\geq 0\text{ and each }w_i\in A\}\)
• 定理：
  • 如果 \(A\) 和 \(B\) 是正则语言，则 \(A\cup B\)、\(A\circ B\)、\(A^*\) 也是正则语言
• claim：如果 NFA \(M\) accepts \(w\)，则转为的 DFA \(M'\) accepts \(w\)，反之也成立
  • Corollary：a language is regular \(\iff\) it is accepted by some DFA

Pumping Theorem¶

可以用来证明一个语言不是正则语言的一个定理。其内容如下：

• 令 \(L\) 为一个正则语言
• 则存在一个整数 \(p\geq 1\)（称为 pumping length）
• 使得对于所有长度不小于 \(p\) 的字符串 \(w\in L\)
• 都可以将 \(w\) 分解为三部分 \(w=xyz\)，满足：
  1. 对于任意 \(k\geq 0\)，有 \(xy^kz\in L\)
  2. \(|y|\geq 1\)
  3. \(|xy|\leq p\)

正则表达式 ¶

一个正则表达式由以下规则定义：

• 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_1R_2\) 对应语言 \(L(R_1R_2) = L(R_1)\circ L(R_2)\)
  • \(R_1^*\) 对应语言 \(L(R_1^*) = L(R_1)^*\)
  • 优先级：\(^* > \circ > \cup\)
    • Ex. \(ab^*\cup b^*a=\big(a(b^*)\big)\cup\big((b^*)a\big)\)

其实就类似于各编程语言中使用的正则表达式，不过那些正则表达式一般都加了不属于这里规定的正则表达式的更多功能（比如记录捕获组并在 \1 时引用捕获内容）。

一般用 \(R\) 表示正则表达式，用 \(L(R)\) 表示正则表达式对应的语言（匹配的字符串集合）。

• 给定一个 NFA \(M\)，要找一个正则表达式 \(R\) 使得 \(L(R) = L(M)\)
• 考虑化简 \(M\)，且需要满足要求：
  • 初始状态没有入边
  • 只有一个没有出边的接受状态
• 化简思路：加一个初始状态和接受状态，用 \(e\)-transition 连接到原来的初始状态和接受状态，然后删除原来的初始状态和接受状态，再逐一删除中间状态