术语表
1 A
Alphabet / 字母表
有限非空的符号集合，通常记为 \(\Sigma\)。
Automaton / 自动机
根据输入和当前状态按规则改变状态的抽象计算模型。
2 C
Concatenation / 联接
把两个字符串首尾相接得到新串的操作。
Counterexample / 反例
用来推翻全称命题的具体失败对象。
3 D
Decision problem / 判定问题
答案为 YES/NO 的计算问题；可通过编码把 YES 实例表示成语言。
4 E
Empty string / 空串
长度为 0 的唯一字符串，记为 \(\varepsilon\)。
5 I
Induction / 归纳法
从基础情况和保持步骤推出无限多个情况成立的证明方法。
6 L
Language / 语言
某个字母表上所有有限串集合 \(\Sigma^*\) 的任意子集。
7 S
State / 状态
系统为了决定未来行为而保留的、对过去历史的有效摘要。
String / 串
字母表中符号组成的有限序列。
Structural induction / 结构归纳
沿递归结构的生成规则证明所有结构对象具有某性质的方法。
8 D
DFA / 确定型有穷自动机
五元组 \((Q,\Sigma,\delta,q_0,F)\)，其中 \(\delta:Q\times\Sigma\to Q\)。每个“当前状态 + 输入符号”唯一决定下一状态。
Dead state / 死状态
进入后无法再到达接受状态、通常对所有输入自环的失败状态。子集构造中的 \(\varnothing\) 常自然对应死状态。
9 E
Extended transition function / 扩展转移函数
把单字符转移扩展到完整输入串的函数，通常记为 \(\hat\delta\)。
Epsilon transition / ε 转移
不消耗任何输入符号就改变状态的转移。
Epsilon closure / ε-闭包
从某状态或状态集合出发，仅沿零条或多条 ε 边可达的所有状态。
10 N
NFA / 非确定型有穷自动机
转移函数返回状态集合的有穷自动机。给定输入时同时保留所有可能路径，只要至少一条路径最终接受就接受。
11 S
Subset construction / 子集构造
把 NFA 转换为等价 DFA 的标准方法。DFA 的一个状态代表 NFA 当前所有可能状态的集合。
12 T
Transition graph / 转移图
用节点表示状态、用带输入标签的有向边表示转移的自动机图形表示。
Transition table / 转移表
按“状态 × 输入符号”列出转移结果的表格表示。
13 R
Regular expression / 正则表达式
由空语言、空串、字母以及并、连接、Kleene 星递归构成的语言表示式。
Recursive language / 递归语言（可判定语言）
存在对所有输入都停机的图灵机判定器的语言。
Recursively enumerable language / 递归可枚举语言（可识别语言）
存在图灵机识别器；成员最终接受，非成员可能不停机。
Reduction / 归约
把一个问题实例有效变换为另一个问题实例，用于比较问题难度。
14 C
Context-free grammar (CFG) / 上下文无关文法
产生式左部为单个变量的四元组文法模型。
Context-free language (CFL) / 上下文无关语言
由某个 CFG 生成、等价地由某个 NPDA 识别的语言。
Chomsky normal form (CNF) / 乔姆斯基范式
CFG 的标准形式，产生式主要为 A→BC 或 A→a。
15 P
Pushdown automaton (PDA) / 下推自动机
有限控制器配合一个栈的自动机模型，表达能力等价于 CFG。
P / 多项式时间类
可由确定型算法在多项式时间内判定的语言类。
NP / 非确定型多项式时间类
可由非确定型多项式时间 TM 接受，等价地具有多项式长度可验证证书的语言类。
NP-complete / NP 完全
既属于 NP，又对所有 NP 问题都是多项式归约意义下至少同样困难的问题。
PSPACE / 多项式空间类
可用多项式工作空间判定的语言类。
16 T
Turing machine / 图灵机
具有有限状态控制、可读写带和读写头的通用计算模型。
17 A
Ambiguous grammar / 歧义文法
存在某个字符串具有两棵不同语法分析树的 CFG。
18 R
RP
多项式时间随机化语言类之一，典型定义具有单侧错误。
ZPP
零错误、期望多项式时间的随机化复杂度类。