DFA 是一个五元组：M = (K, Σ, δ, s, F)
配置 (q, w) ∈ K × Σ∗
M 在一步内产生: ⊢ᴍ
M 产生: ⊢ᴍ∗
NFA 是一个五元组：M = (K, Σ, Δ, s, F)
配置 (q, w) ∈ K × Σ∗
M 在一步内产生: ⊢ᴍ
M 产生: ⊢ᴍ∗
定理: 任何 NFA M 都可以找到一个 DFA M′ 使得 L(M) = L(M′)
构造思路：
⚠️ 注意: 画 DFA 时，任何状态都要包含所有可能 symbol 的对应关系
即 ∀p ∈ K, ∀c ∈ Σ, ∃q ∈ K 使得 δ(p, c) = q
如果一个语言可以被某个 DFA 或 NFA 接受，则它是正则语言
正则语言的封闭性：
注意: A - B = A ∩ B̄，因此如果 ∩ 和 Ā 都封闭，则差运算也封闭
用于描述正则语言
优先级: ∗ > ∘ > ∪
定理: 任何 NFA M 都能找到一个正则表达式 R 使得 L(M) = L(R)，反之亦然
定理: 若 L 是一个正则语言，则存在泵长度 p ∈ ℤ∗ 使得 ∀w ∈ L 且 |w| ≥ p，w 可被分为三部分 w = xyz，满足：
泵引理是 RL 的一个必要不充分条件
应用示例: 证明 {0ⁿ1ⁿ : n ≥ 0} 不是正则的
证明思路：假设 L 是 RL，设泵长度为 p，构造一个含 p 且属于 L 的字符串，证明它不符合泵引理
常见非正则语言及证明思路：
问题: 写出表示 {w ∈ {a,b}∗: w 中 b 的数量可被 3 整除} 的正则表达式
答案: a∗ ∪ (a∗ba∗ba∗ba∗)∗
解释:
转换思路：
转换模式：
如果状态 q 有从 p 到 q 的边标记为 A，从 q 到 r 的边标记为 B，q 的自环标记为 C，则删除 q 后添加从 p 到 r 的边标记为 AC∗B
以下关系等价：
这些等价关系在证明语言属性时非常有用
每个判定问题都对应一个语言
重要概念：
空字符串 ε 是任何字母表 Σ 上的字符串，但不在 Σ⁺ 中
RL 和 Non-RL、Non-RL 和 Non-RL 的连接都可能是 RL
例子：
关键点：正则语言类在适当运算下封闭，但非正则语言类的运算结果不确定
泵引理只能用于证明语言不是正则的
如果一个语言满足泵引理条件，不能断定它是正则的
反例：存在非正则语言满足泵引理条件
因此，泵引理是正则语言的必要不充分条件
策略：
记忆提示：多思考 {0ⁿ1ⁿ} 不是正则的例子
常见技巧：通过已知非正则语言构造矛盾