形式文法

---

用于生成语言中的合格句子，并排除不合格句子的一套数目有限的规则的集合。它山初始符号S、非终极符号V_N、终极符号V_T和改为规则P四个部分组成，记为：G=(V_N，V_T，S，P)。句子的生成，表现为从初始符号开始，反复应用改写规则，直到得到一个不能再继续改写的终极符号串(string)为止。这个过程叫做推导史，这个终极符号串就是语言中的一个合格的句子。如假定汉语中有如下的文法：

G=(V_N、V_T、S、P)

V_N=｛NP、VP、D、N、V｝

V_T=｛小红、小张、孩子、这、那、一本、一个、两本、两个、买、卖、踢、玩、读、书、球……｝

利用这个文法可以生成诸加”小红读书”、”小张买一本书”、”这孩子玩皮球”之类合格的句子。如”小红读书”这个句子的生成过程如下：

按照形式文法的生成力量，可把它们分为四个类型，即^*0型文法、^*1型文法、^*2型文法、^*3型文法。每一类型都由它所包含的改写规则来定义。0型是力量最强的，随著数目的递增，力量就越来越受限制。各类型文法之间的关系是：力量较强的文法包含著力量较弱的文法，即能用力量较弱的文法生成的语言，一定能用力量较强的文法生成，反过来就不一定。