正则语言能描述固定模式，但「我看见你用望远镜」至少两种合法切分——自然语言的歧义超出了正则的承受范围。

上页我们说，没有形式化就只能凭语感。这页给「形式文法」一个严格的数学骨架——四元组 G = (V, T, P, S)。四个分量各司其职，少一个就无法精确刻画语言。

自上而下逐层加约束，约束越多能力越弱；四层语言类嵌套包含：3 ⊂ 2 ⊂ 1 ⊂ 0。

最左推导、最右推导与语法树

从派生树的形态看，3 型文法对应的树最瘦——每个内部节点至多只有两个子节点。这个直观特征背后，是产生式右部「至多含一个非终结符」的硬约束。先把这条规则钉死。

左线性与右线性生成的语言完全相同，但产生式形态和推导方向像镜像——容易混淆，一页辨清。

左线性、右线性强制递归只能贴在一端。但 aⁿbⁿ 这类嵌套结构要求非终结符夹在中间——必须把限制放宽，这就是上下文无关文法。

上页我们区分了左线性与右线性的形态差别。现在给出正则文法的严格定义，看它到底产生什么样的语言——也就是我们要找的「正则语言」这个语言类。

线性文法造出正则语言，那语言之间怎么运算？三种基本操作——并、连接、闭包——就能由小拼大。

用 Python 把右线性文法 S→aA|a, A→bA|b 一步步化简为正则表达式 a b*, 并用 re 模块验证。

四步构造: 产生式列方程 → Arden 引理解递归项 → 回代并用 b+ + ε = b* 化简 → re.fullmatch 双端锚定验证正反例, 得 L(G)=ab*。

G ⟺ NFA：每个产生式对应一条状态转移，反向亦然；两者刻画同一正则语言 L。

正则文法、自动机、正则表达式殊途同归，描述同一类语言。但遇到陌生语言，怎么证明它不是正则的？两个正则语言做并、交、补，结果还是正则的吗？

正则语言是 CFL 的严格子集，但很多人误以为能力差不多，边界案例最容易踩坑。

判一个语言是否正则，单台DFA就够;但要证正则语言对交集、并集封闭，得把两台DFA「叠」成一台同步跑的机器。这一页就来构造这种积自动机。

从两个 DFA 出发，沿箭头看构造的五步流水线：五元组 → 笛卡尔积 → 转移 → 初/终态 → 交集识别。

以两个简单 DFA 为例，演示积自动机的完整构造——从状态对到转移再到终态确认。

上一页我们手工搭了一台积自动机，它到底有什么用？这页揭晓——它解决正则语言三大封闭运算中的交运算；并与补各有更简便的招数。

• ✓正则语言由文法、表达式、自动机三种方式等价刻画
• ✓泵引理划定能力边界，是证非正则的统一工具
• ✓左/右线性文法等价，仅派生方向相反
• ✓Chomsky层级中表达力递增，可判定性同步下降
• ✓积自动机把并/交/差运算转成可构造状态机

以下关于正则语言的说法，哪个是正确的？

先自己想，再看下面的参考答案。