自然语言处理二——乔姆斯基四型文法

一、正则文法（3型）

Definition ：假设有一个文法G=(N, Σ, P, S)，其中P中的产生式遵循以下两种形式之一：

1. A→Bx（此处B仅作为一个形式标记，并不代表实际的非终结符），或者
2. A→x，
   其中A和B属于非终结符集合N（N），x属于输入符号集合Σ，则称此文法为正则文法（亦可简记为FSG），并归类于第三类语法体系。（左线性正则文法）若产生式的形式为A→xB，则相应的正则文法则被称为右线性正则文法。（注：“这里的‘注意’已经被省略。”）

例如有如下规则：A→ A x，A → x。那么可以推出A

Axx，A

Axxx，......A

![\Rightarrow](https://ad.itadn.com/c/weblog/blog-img/images/2025-06-01/vFTqgfrR9Z4D