第十四课：语言分析、自动机

有限状态机

基本概念

• 有限状态机：有穷个状态的机器
• 输入符号 → 状态转移 → 输出（或接受/拒绝）

确定型有限自动机（DFA）

• 五元组：⟨Q, Σ, δ, q₀, F⟩
• Q：状态的有限集合
• Σ：输入字母表
• δ：转移函数 δ:Q×Σ→Q
• q₀：初始状态
• F：接受状态集合
• 确定性：每个状态对每个输入有唯一转移

非确定型有限自动机（NFA）

• 一个状态对同一输入可以有多个转移
• 允许ε转移（不读入字符就转移）
• NFA和DFA等价（可以相互转化）

正则语言

• 能被有限自动机识别的语言 = 正则语言
• 正则语言 = 能用正则表达式描述的语言

泵引理 ⭐

• 用于证明某语言不是正则语言
• 基本思想：足够长的字符串必然有重复的模式
• 例：L={aᵐbᵐ | m>0}不是正则语言
• 假设是正则的，取s=aᵖbᵖ（p为泵长度）
• 将s分成s=xyz，其中y≠ε，|xy|≤p
• 则y只包含a，泵入得到a^(p+k)b^p
• 不再满足a和b数量相等 → 矛盾

💡 人话：泵引理说"足够长的正则语言的字符串一定有一段可以重复"。如果某个语言不允许这种重复，它就不可能是正则语言。