结论44 Chomsky的文法体系: 对于文法G=(∑,Ⅴ,S,P),根据对产生式 的不同限制, Chomsky将文法分为四类: ●文法G是3型文法,即右线性文法; ●文法G是2型文法,即上下文无关文法; ●文法G是1型文法,即上下文相关文法 ●文法G是0型文法,文法对产生式没有任何限制;
⚫ 结论4-4 Chomsky的文法体系： ⚫ 对于文法G=（∑，V，S，P），根据对产生式 的不同限制，Chomsky将文法分为四类： ⚫ 文法G是3型文法，即右线性文法； ⚫ 文法G是2型文法，即上下文无关文法； ⚫ 文法G是1型文法，即上下文相关文法； ⚫ 文法G是0型文法，文法对产生式没有任何限制；
语言的分类是根据产生该语言的文法的分类进行的。若一个 语言L由某个i文法产生,则它是语言。i=0,12,3。即 语言L是3型语言,即右线性语言;若L能由某个3型文法产 生 语言L是2型语言,即上下文无关语言;若L能由某个2型文 法产生。 语言L是1型语言,即上下文相关语言;若L能由某个1型文 法产生。 语言L是0型语言,即短语结构语言(PSL或递归可枚举集, 若L能由某个0型文法产生
⚫ 语言的分类是根据产生该语言的文法的分类进行的。若一个 语言L由某个i型文法产生，则它是i型语言。i=0,1,2,3。即 ⚫ 语言L是3型语言，即右线性语言；若L能由某个3型文法产 生。 ⚫ 语言L是2型语言，即上下文无关语言；若L能由某个2型文 法产生。 ⚫ 语言L是1型语言，即上下文相关语言；若L能由某个1型文 法产生。 ⚫ 语言L是0型语言，即短语结构语言(PSL)或递归可枚举集， 若L能由某个0型文法产生
定义4-5文法分类定义 用ψ1(语言类)的概念来定义所有的i型语言;对 于0≤≤3 甲;={LC∑=L(G),G是i型文法}
⚫ 定义4-5 文法分类定义 ⚫ 用Ψi（语言类）的概念来定义所有的i型语言；对 于0≤i≤3 ⚫ Ψ i ={LС∑*|L=L（G），G是i型文法}
●定理4-6语言分类定理 Chomsky将语言分为四类,且有包含关系(真子集 关系): ●v3cv2cv1cv
⚫ 定理4-6 语言分类定理 ⚫ Chomsky将语言分为四类，且有包含关系（真子集 关系）： ⚫ Ψ3СΨ2СΨ1 СΨ0
·42 Chomsky的文法体系另一种描述 目前,国内普遍对 Chomsky的文法体系存在另外 种描述方式,该方式限制了一般的空串产生式 的使用。 对于一般的短语结构文法,G=(∑,V,S,P): G称为0型文法,或短语结构文法PSG)。对应的 L(G叫作0型语言或者短语结构语言PSL、递归 可枚举集
⚫ 4.2 Chomsky的文法体系另一种描述 ⚫ 目前，国内普遍对Chomsky的文法体系存在另外 一种描述方式，该方式限制了一般的空串产生式 的使用。 ⚫ 对于一般的短语结构文法，G=(∑，V，S，P)： ⚫ G称为0型文法，或短语结构文法(PSG)。对应的 L(G)叫作0型语言或者短语结构语言(PSL)、递归 可枚举集