Skip to main content

1 / 4概念

Automata & Formal Languages

自动机是“带多少记忆的识别器”,形式语言是“它能识别的字符串集合”。判断标准不是“正则更简单”,而是语言需不需要计数、嵌套或栈;选错层级,正则会写出回溯灾难,语法分析器会为简单 token 付出过高代价。

1 概念​

1.1 一句话定义​

自动机是有限状态 + 转移规则的计算模型;形式语言是某个字母表上字符串的集合。DFA/NFA 识别正则语言,CFG/PDA 识别上下文无关语言,图灵机识别递归可枚举语言;乔姆斯基谱系按“记忆能力”从弱到强排列。

1.2 它解决什么问题​

  • 词法分析:标识符、数字、关键字是正则语言,DFA 可以线性扫描。
  • 语法分析:括号、嵌套、表达式优先级需要栈,CFG/PDA 才能表达。
  • 协议与状态机:登录、订单、连接生命周期可以用有限状态机建模并验证。
  • 边界判断:先判断语言属于哪一层,再决定用正则、解析器还是通用程序。

1.3 不属于本页的内容​

主题去哪
图灵机、可计算性、停机问题Computability
P/NP、NP 完全性Computational Complexity
编译器前端的完整实现编译原理相关页面(待补)
正则引擎的工程实现与优化文本处理/正则工程页面(待补)
模型检验与形式化验证形式化方法页面(待补)

1.4 关键术语​

术语含义容易混淆的点
字符串 / 语言符号序列 / 字符串集合空串 ε 不是空语言 ∅
DFA确定性有限自动机,每个状态每个符号唯一转移转移函数是全函数
NFA非确定性有限自动机,可有 ε 转移和多个后继与 DFA 等价,不是更强
子集构造把 NFA 状态集合变成 DFA 状态最坏 2ⁿ 个状态
正则表达式用并、连接、闭包描述正则语言工程正则常带反向引用,超出理论正则
CFG上下文无关文法,产生式左部是单个非终结符不是“所有语法”
推导 / 分析树从开始符号展开得到字符串歧义是两棵不同分析树
PDA下推自动机,带一个栈非确定 PDA 比确定 PDA 强
泵引理证明语言不属于某层的必要条件不是充分条件,不能证明属于