第十三课：代数结构、同态映射、形式语言

代数结构基础

代数系统

• 代数系统⟨S,∗⟩：非空集合S和二元运算∗
• 封闭性：∀a,b∈S, a∗b∈S
• 结合律：∀a,b,c∈S, (a∗b)∗c = a∗(b∗c)
• 交换律：∀a,b∈S, a∗b = b∗a

半群、独异点、群

结构	定义	例子
半群	封闭 + 结合律	⟨N,+⟩
独异点	半群 + 有幺元	⟨N,×⟩（幺元1）
群	独异点 + 每个元素有逆元	⟨Z,+⟩

• 幺元e：∀a∈S, a∗e = e∗a = a
• 逆元a⁻¹：a∗a⁻¹ = a⁻¹∗a = e

同态与同构 ⭐

同态映射

• f:⟨S,∗⟩→⟨T,△⟩
• 条件：f(a∗b) = f(a)△f(b)
• 运算结构被保持

同构

• 同构 = 双射的同态
• 同构的两个代数系统具有完全相同的结构（只是符号不同）

经典例子： - f(x)=2ˣ 是 ⟨R,+⟩ 到 ⟨R⁺,×⟩ 的同构 - f(a+b) = 2^(a+b) = 2ᵃ×2ᵇ = f(a)×f(b) ✓ - 双射 ✓

💡 人话：同态就是"映射保持运算"——先运算再映射 = 先映射再运算。同构就是"换个名字但从结构上看完全一样"。

形式语言

基础概念

• 字母表Σ：符号的有限集合
• 字符串（单词）：字母表上符号的有限序列
• 语言：字母表上字符串的集合

正则表达式

• 用运算符描述语言：
• 并：L₁∪L₂
• 连接：L₁·L₂
• Kleene闭包：L*（零次或多次重复）
• 例子：
• 不包含连续两个b的字符串
• 以bb结尾的字符串