某些文法不满足上述3类文法的要求;如 s→AB1 AB0 该文法不是右线性文法,不是无关文法,也不是 相关文法,只能属于短语结构文法
⚫ 某些文法不满足上述3类文法的要求；如 ⚫ S→AB1 ⚫ AB→0 ⚫ 该文法不是右线性文法，不是无关文法，也不是 相关文法，只能属于短语结构文法
● Chomsky将文法分为四类,关系为: 任意一个右线性文法本身是一个无关文法;本身 不一定是相关文法; ●任意一个无关文法本身不一定是相关文法;
⚫ Chomsky将文法分为四类，关系为： ⚫ 任意一个右线性文法本身是一个无关文法；本身 不一定是相关文法； ⚫ 任意一个无关文法本身不一定是相关文法；
设文法G=(∑,V,S,P),则判断G是哪类文法的方法如下 1、G是短语结构文法; 2、如果所有产生式都有右边部分长度大于等于左边部分,那么 G是上下文有关文法; 3、如果如果所有产生式的左边部分都是单个非终极符号,那么 G是上下文无关文法; 4、如果所有产生式的右边部分都是以终极符号开始、含有至多 个非终极符号、如果有非终极符号则出现在最右边,那么G 是正则文法
⚫ 设文法G=(∑，V，S，P)，则判断G是哪类文法的方法如下： ⚫ 1、G是短语结构文法； ⚫ 2、如果所有产生式都有右边部分长度大于等于左边部分，那么 G是上下文有关文法； ⚫ 3、如果如果所有产生式的左边部分都是单个非终极符号，那么 G是上下文无关文法； ⚫ 4、如果所有产生式的右边部分都是以终极符号开始、含有至多 一个非终极符号、如果有非终极符号则出现在最右边，那么G 是正则文法
41.2语言之间的关系 下面讨论语言之间的关系。 ●任意一个右线性语言文法本身是一个无关语言; 个上下文无关语言是不是一个上下文相关语言呢? 从第二章可知:一个无关文法 ●①没有任何空串产生式,或者 ②仅有一个空串产生式S→E,且S不出现在任何产生式的右 边 ●则该文法本身就是一个相关文法;它产生的无关语言也就是 个相关语言;那么,如果 关文法中有般的空串产 生式如A一E,A是一个非终结 且不是开始符号),它 产生的无关语言是不是相关语言呢?
⚫ 4.1.2语言之间的关系 ⚫ 下面讨论语言之间的关系。 ⚫ 任意一个右线性语言文法本身是一个无关语言； ⚫ 一个上下文无关语言是不是一个上下文相关语言呢？ ⚫ 从第二章可知：一个无关文法 ⚫ ①没有任何空串产生式，或者 ⚫ ②仅有一个空串产生式S→ε，且S不出现在任何产生式的右 边 ⚫ 则该文法本身就是一个相关文法；它产生的无关语言也就是 一个相关语言；那么，如果一个无关文法中有一般的空串产 生式（如A→ε，A是一个非终结符，且不是开始符号），它 产生的无关语言是不是相关语言呢？
据空甲定理: G是一个上下文无关文法,存在一般的空串产生式A→E,则 存在另一个上下文无关文法G使得: (1)L(G)=L(G); (2)若E!∈L(G),则G中没有任何空串产生式; (3若E∈L(G),则G中有一个空串产生式,S'→E,且S不出 现在G的其它任何产生式的右边;(S是G开始符号) 实际上,G是一个无关文法。也是一个相关文法。 即:任意一个无关文法都可以改造为等价的一个相关文法, 所以,在意一个无关语言也 相关语言
⚫ 根据空串定理： ⚫ G是一个上下文无关文法，存在一般的空串产生式A→ε，则 存在另一个上下文无关文法G′使得： ⚫ ⑴L(G)=L(G′)； ⚫ ⑵若ε！∈L(G)，则G′中没有任何空串产生式； ⚫ ⑶若ε∈L(G)，则G′中有一个空串产生式，S′→ε，且S′不出 现在G′的其它任何产生式的右边；（S′是G′开始符号） ⚫ 实际上，G’是一个无关文法。也是一个相关文法。 ⚫ 即：任意一个无关文法都可以改造为等价的一个相关文法， 所以，任意一个无关语言也是一个相关语言