符号表
1 第 1 章已引入符号
| 符号 | 含义 | 备注 |
|---|---|---|
| \(\Sigma\) | 字母表 | 有限非空符号集合 |
| \(a,b,c\) | 符号 | 通常表示字母表中的单个元素 |
| \(w,x,y,z\) | 串 | 字母表上符号的有限序列 |
| \(\varepsilon\) | 空串 | 唯一长度为 0 的串 |
| \(|w|\) | 串 \(w\) 的长度 | 若对象为集合，竖线也常表示基数 |
| \(xy\) | 串联接 | 一般不满足交换律 |
| \(w^k\) | \(w\) 重复联接 \(k\) 次 | \(w^0=\varepsilon\) |
| \(\Sigma^k\) | \(\Sigma\) 上长度恰为 \(k\) 的串集合 | \(\Sigma^0=\{\varepsilon\}\) |
| \(\Sigma^*\) | \(\Sigma\) 上所有有限串 | 包含 \(\varepsilon\) |
| \(\Sigma^+\) | \(\Sigma\) 上所有非空有限串 | \(\Sigma^*\setminus\{\varepsilon\}\) |
| \(L\) | 语言 | \(L\subseteq\Sigma^*\) |
| \(\varnothing\) | 空集合 | 与 \(\varepsilon\) 不同 |
| \(\{\varepsilon\}\) | 只含空串的语言 | 与 \(\varnothing\) 不同 |
| \(\in\) | 属于 | 元素与集合之间 |
| \(\subseteq\) | 子集 | 集合与集合之间 |
| \(\cup\) | 并集 | |
| \(\cap\) | 交集 | |
| \(P\Rightarrow Q\) | 如果 \(P\)，则 \(Q\) | 蕴含 |
| \(P\iff Q\) | \(P\) 当且仅当 \(Q\) | 两个方向都要证明 |
| \(\neg P\) | 非 \(P\) | 否定 |
| \(\forall\) | 对所有 | 全称量词 |
| \(\exists\) | 存在 | 存在量词 |
2 第 2 章新增符号
| 符号 | 含义 | 备注 |
|---|---|---|
| \(Q\) | 状态集合 | 有穷集合 |
| \(q_0\) | 初始状态 | \(q_0\in Q\) |
| \(F\) | 接受状态集合 | \(F\subseteq Q\) |
| \(\delta\) | 单步转移函数 | DFA 返回一个状态；NFA 返回状态集合 |
| \(\hat\delta\) | 扩展转移函数 | 处理整个字符串 |
| \(A=(Q,\Sigma,\delta,q_0,F)\) | DFA/NFA 五元组 | 具体函数类型依模型而异 |
| \(L(A)\) | 自动机 \(A\) 接受的语言 | DFA: \(\hat\delta(q_0,w)\in F\) |
| \(2^Q\) | \(Q\) 的幂集 | NFA 转移值和子集构造状态空间 |
| \(S\cap F\neq\varnothing\) | 状态集合中至少含一个接受状态 | NFA / subset DFA 接受条件 |
| \(\operatorname{ECLOSE}(q)\) | 状态 \(q\) 的 ε-闭包 | 包含 \(q\) 自身 |
| \(\operatorname{ECLOSE}(S)\) | 集合 \(S\) 的 ε-闭包 | 各状态闭包之并 |
| \(\#_a(w)\) | 串 \(w\) 中符号 \(a\) 的出现次数 | 项目补充记号，用于设计说明 |
3 第 3–11 章新增常用符号
| 符号 | 含义 |
|---|---|
| \(R,S,T\) | 正则表达式或其表示的语言（上下文决定） |
| \(L(R)\) | 正则表达式 \(R\) 表示的语言 |
| \(G=(V,T,P,S)\) | 上下文无关文法 |
| \(\Rightarrow,\Rightarrow^*\) | 文法一步/多步推导 |
| \(P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)\) | PDA |
| \(\Gamma\) | 栈字母表或图灵机带字母表（上下文决定） |
| \(\vdash,\vdash^*\) | 机器配置一步/多步移动 |
| \(M\) | 图灵机 |
| \(\langle M,w\rangle\) | 图灵机及输入的编码 |
| \(A_{TM}\) | 图灵机接受问题语言 |
| \(\le_m\) | 可计算多一归约 |
| \(\le_p\) | 多项式时间归约 |
| \(P,NP,coNP\) | 复杂度类 |
| \(PSPACE\) | 多项式空间复杂度类 |
| \(RP,ZPP\) | 随机化复杂度类 |