乔姆斯基范式的定义

乔姆斯基范式的定义《理论计算机科学基础》1《理论计算机科学基础》2乔姆斯基范式(CNF)CNF:只允许如下形式的规则:S

ABCAa其中A,B,C是任意变元B,C不是初始变元

(初始变元不能在右方出现)a是任意终结符求乔姆斯基范式的算法《理论计算机科学基础》3《理论计算机科学基础》4乔姆斯基范式(CNF)等价:

两个文法生成同样语言定理3.6:任何CFG都有

等价的CNF.《理论计算机科学基础》5定理3.6定理3.6:任何CFG都有

等价的CNF.证明思路:下列算法：1)添加新的初始变元2)处理A(规则)3)处理AB(单一规则)4)处理Au1u2…uk

(k3)5)处理Aaiaj,AaiB,ABai《理论计算机科学基础》6添加新初始变元1)添加新初始变元S0和规则S0S,

其中S是旧初始变元.《理论计算机科学基础》7处理规则2)考虑所有规则.若A不是初始变元,则删除A

,以各种可能的方式删除其他规则右边的A,添加新的规则,例如由BuAv添加Buv由BuAvAw添加BuvAw|uAvw|uvw由BA添加B(除非已删除过B)直到删除所有规则(S0

除外)为止.《理论计算机科学基础》8处理单一规则3)处理所有单一规则.

删除AB,

若有规则Bu,则添加规则Au,

除非Au是已删除过的单一规则.

重复上述步骤,

直到删除所有单一规则为止.《理论计算机科学基础》9处理Au1u2…uk规则4)把每一条规则Au1u2…uk换成Au1A1A1u2A2

A2u3A3…Ak-2uk-1uk(k3)《理论计算机科学基础》10处理终结符5)对每个终结符ai，

引入变元Ui和规则Uiai.把Aaiaj换成AUiUj把AaiB换成AUiB把ABai换成ABui可以证明，这样求出的是等价的乔姆斯基范式

，

定理3.6证明完毕。求乔姆斯基范式的例子《理论计算机科学基础》11《理论计算机科学基础》12例3.7G6:SASA|aB,AB|SBb|

求等价CNF.《理论计算机科学基础》13例3.7(1)G6:SASA|aB,AB|SBb|

(1)S0SSASA|aBAB|SBb|

《理论计算机科学基础》14例3.7(2a)(2a)S0SSASA|aBAB|SBb|

《理论计算机科学基础》15例3.7(2a)(2a)S0S

SASA|aB|aAB|S|

Bb《理论计算机科学基础》16例3.7(2b)(2b)S0S

SASA|aB|aAB|S|

Bb《理论计算机科学基础》17例3.7(2b)(2b)S0S

SASA|aB|a|SA|AS|SAB|S

Bb《理论计算机科学基础》18例3.7(3a)(3a)

S0SSASA|aB|a|SA|AS|SAB|SBb《理论计算机科学基础》19例3.7(3a)(3a)

S0SSASA|aB|a|SA|ASAB|SBb《理论计算机科学基础》20例3.7(3b)(3b)

S0

SSASA|aB|a|SA|ASAB|SBb《理论计算机科学基础》21例3.7(3b)(3b)

S0

ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBb《理论计算机科学基础》22例3.7(3c)(3c)

S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBb《理论计算机科学基础》23例3.7(3c)(3c)

S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAS|bBb《理论计算机科学基础》24例3.7(3d)(3d)

S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAS|bBb《理论计算机科学基础》25例3.7(3d)(3d)

S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|ASA|aB|a|

SA|ASBb《理论计算机科学基础》26例3.7(4)(4)

S0

ASA|aB|a|SA|AS

S

ASA|aB|a|SA|ASAb|ASA|aB|a|SA|ASBb《理论计算机科学基础》27例3.7(4)(4)

S0

AA1|aB|a|SA|ASS

AA2|aB|a|SA|ASAb|AA3|aB|a|SA|ASBb

A1SA

A2SAA3SA《理论计算机科学基础》28例3.7(4)(4)

S0

AA1|aB|a|SA|ASS

AA1|aB|a|SA|ASAb|AA1|aB|a|SA|ASBb

A1SA《理论计算机科学基础》29例3.7(5)(5)

S0AA1|aB|a|SA|ASSAA1|aB|a|SA|ASAb|AA1|aB|a|SA|ASBbA1SA《理论计算机科学基础》30例3.7(5)-完成(5)

S