Chomsky将文法分为四类（0型到3型），其中**正规文法（正则文法）对应的是3型文法*

Chomsky将文法分为四类0型到3型其中正规文法正则文法对应的是3型文法。3型文法的产生式形式严格受限分为两种等价形式左线性或右线性右线性文法形如 $ A \to aB $ 或 $ A \to a $其中 $ A, B $ 是非终结符$ a $ 是终结符或空串 $ \varepsilon $若允许 $ \varepsilon $-产生式则需注意起始符不递归产生空串左线性文法形如 $ A \to Ba $ 或 $ A \to a $。3型文法生成的语言恰好是正则语言可被有限自动机DFA/NFA识别也可用正则表达式描述。左线性文法和右线性文法生成的语言类完全相同根本原因在于二者均可被确定性有限自动机DFA等价识别且彼此可通过文法变换相互转换不改变所生成的语言类即正则语言类。具体解释如下✅形式语言层面的等价性右线性文法天然对应“从左到右扫描输入、状态随字符转移”的DFA/NFA建模方式非终结符对应状态产生式 $ A \to aB $ 对应转移 $ \delta(A, a) BA \to a $ 对应接受态左线性文法如 $ A \to Ba $看似“从右向左构造”但其生成的字符串可看作是某右线性文法生成字符串的逆序。关键在于正则语言在逆序reverse运算下封闭——若 $ L $ 是正则语言则 $ L^R { w^R \mid w \in L } $ 也是正则语言。因此对任意左线性文法 $ G $其生成语言 $ L(G) $ 满足 $ L(G) (L(G’))^R $其中 $ G’ $ 是某右线性文法而因 $ L(G’) $ 正则 ⇒ $ (L(G’))^R $ 正则 ⇒ $ L(G) $ 正则。反之亦然。✅构造性证明双向转换左线性 → 右线性可先将左线性文法的每个产生式 $ A \to Ba $ 反转为 $ A’ \to aB’ $引入新非终结符并反转符号顺序再调整起始符和接受规则得到等价右线性文法右线性 → 左线性类似地通过符号反转与非终结符重命名实现。注需谨慎处理空串 $ \varepsilon $ 和起始符的终止性但总存在系统化算法完成等价转换。✅自动机视角统一两者都对应有限状态自动机——右线性文法直接模拟NFA的前向转移左线性文法则等价于NFA的逆向转移即构建反向NFA再取逆而NFA的逆转仍为NFA且其所接受语言的逆序仍是正则语言再结合“正则语言类在逆序下封闭”即可推出二者语言类完全重合。综上左、右线性文法虽构造方向不同但表达能力一致共同刻画正则语言类故同属Chomsky 3型文法。