如果对于任意a→>B∈P,均有|β2x成立,则称G为1型文法, 或上下文有关文法(cSG)。对应的L(G叫作1型语言或者上下 文有关语言(csL 如果对于任意a→>β∈P,均有|β≥|a且a∈V成立,则称G为2 型文法,或上下文无关文法(cFG)。对应的L(G叫作2型语言 或者上下文无关语言(cFL) 如果对于任意a→>β∈P,α->B均具有形式A→W,AWB,其中, AB∈V,W∈T+,则称G为3型文法,也可称为正则文法(RG) 或正规文法。对应的LG叫作3型语言,也可称为正则语言 或正规语言(RL)
⚫ 如果对于任意→P，均有||≥||成立，则称G为1型文法， 或上下文有关文法(CSG)。对应的L(G)叫作1型语言或者上下 文有关语言(CSL)。 ⚫ 如果对于任意→P，均有||≥||且V成立，则称G为2 型文法，或上下文无关文法(CFG)。对应的L(G)叫作2型语言 或者上下文无关语言(CFL)。 ⚫ 如果对于任意→P，→均具有形式A→w, A→wB, 其中， A,BV, wT+，则称G为3型文法，也可称为正则文法(RG) 或正规文法。对应的L(G)叫作3型语言，也可称为正则语言 或正规语言(RL)
●正规语言类包含于上下文无关语言类,上下文无关 语言类包含于上下文相关语言类,上下文相关语言 类包含于递归可枚举语言类。这里的包含都是集合 的真包含关系,也就是说:存在递归可枚举语言不 属于上下文相关语言类,存在上下文相关语言不属 于上下文无关语言类,存在上下文无关语言不属于 正规语言类
⚫ 正规语言类包含于上下文无关语言类，上下文无关 语言类包含于上下文相关语言类，上下文相关语言 类包含于递归可枚举语言类。这里的包含都是集合 的真包含关系，也就是说：存在递归可枚举语言不 属于上下文相关语言类，存在上下文相关语言不属 于上下文无关语言类，存在上下文无关语言不属于 正规语言类
●四类文法和对应的四类语言之间都有包含关系
⚫ 四类文法和对应的四类语言之间都有包含关系
定理4-7 是RL的充要条件是存在一个文法,该文法产生语言 L,并且它的产生式要么是形如A-为a的产生式,要么 是形如A→>aB的产生式,其中A、B为语法变量,a 为终极符号 证明: 参考定理2-15的证明
⚫ 定理4-7 ⚫ L 是RL 的充要条件是存在一个文法，该文法产生语言 L， 并且它的产生式要么是形如A→a 的产生式，要么 是形如A→aB 的产生式，其中A、B 为语法变量，a 为终极符号。 ⚫ 证明： ⚫ 参考定理2-15的证明
定义48线性文法的定义。 设文法G=(∑,V,S,P)。如果对于∨α→>β∈P,α→>β均具有 如下形式:A→)W,A→wWBx,其中,A,BeV,WX∈T,则称G 为线性文法。对应地,L(G叫作线性语言。 设文法G=(∑,V,S,P)。如果对于∨α→>β∈P,α→>β均具有 如下形式:A→)WA→wB,其中,A,B∈Vw∈T+,则称G为 右线性文法。对应地,L(G叫作右线性语言。 设文法G=(∑,V,S,P)。如果对于να→>β∈P,α→>β均具有 如下形式:A→>W,A→>Bw,其中,A,B∈V,w∈T+,则称G为 左线性文法。对应地,L(G叫作左线性语言
⚫ 定义4-8 线性文法的定义。 ⚫ 设文法G=(∑，V，S，P)。如果对于→P，→均具有 如下形式：A→w, A→wBx，其中，A,BV, w,xT*，则称G 为线性文法。对应地，L(G)叫作线性语言。 ⚫ 设文法G=(∑，V，S，P)。如果对于→P，→均具有 如下形式：A→w, A→wB，其中，A,BV, wT+，则称G为 右线性文法。对应地，L(G)叫作右线性语言。 ⚫ 设文法G=(∑，V，S，P)。如果对于→P，→均具有 如下形式：A→w, A→Bw，其中，A,BV, wT+，则称G为 左线性文法。对应地，L(G)叫作左线性语言