计算引论8 上下文无关语言识别算法.ppt

《计算引论8 上下文无关语言识别算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算引论第三章文法与语言第三章文法与语言3.1语言的基本概念3.2有限自动机3.3上下文无关语言3.4上下文无关语言识别算法3.4上下文无关语言识别算法定义：任意串ω∈T*，ω=X1X2…Xi…Xi+j-1…Xn，将ω的一个子串Xi…Xi+j-1记为ωij，则有：3.4上下文无关语言识别算法

2、ωij

3、=j(j>0)，为串的长度，且：ω11=X1ω21=X2…ωi1=Xi…ωn1=Xnω1n=X1X2…Xi…Xi+j-1…Xn=ω3.4上下文无关语言识别算法算法设计思想：欲证明Sω，因为任意串均可以转换为乔姆斯范式，有：1、对于

4、ω

5、＝1，则只需

6、要检查(SX1)∈P是否成立即可。3.4上下文无关语言识别算法2、对于

7、ω

8、≥2，设有一个非终极符，则只需证明（S）ω，欲证明S，则应先S两个非终极符，设为BC，即SBC，问题归结为BCω是否成立。3.4上下文无关语言识别算法3、如果BCω成立，可以认为串ω是由两部分组成，一部分由B推出，另一部分由C推出，因此，存在k（k≥1，k≤n-1），使得：Bω1k，从X1开始，长度为kCω(k+1)(n-k)，从Xk+1开始，长度为n-k当k=1时，则Bω11，同情况1。3.4上下文无关语言识别算法4、问题分析抽象：对串ωij,如果存在

9、k(k≥1，k≤j-1)，BC∈V，使得：ABC∈P，且Bωik，Cω(i+k)(j-k)，则：Aωij特别地，若A=S，i=1，j=n，则可证明Sω记Vij={A

10、Aωij}，该集合中的任何一个非终极符均可以推导出ωij即Vij={A

11、(ABC)∈P，且B∈Vik，C∈V(i+k)(j-k)}，其中k>0，k

12、Aω11}={A

13、(AX1)∈P}…Vj1={A

14、(AXj)∈P}…Vn1={A

15、(AXn)∈P}3.4上下文无关语言识别算法Vij可以由V11，V21，…，Vn1

16、，V12，V22，…，Vn2，…等集合组成。上表构造出各个不同行的非终极符集合。3.4上下文无关语言识别算法5、检查S∈V1n是否成立（即Sω），如果成立，则说明ωik均可以由S推出，且能够找出所有的推导路径，从而找到最短的路径。3.4上下文无关语言识别算法例：G=({A,B,C,S},{a,b},P,S)其中：P中的产生式集合为：{SAB,SBC,BCC,Bb,CAB,Ca,ABA,Aa}请说明S根据文法规则推导出ω=baaba3.4上下文无关语言识别算法X1=b,X2=a,X3=a,X4=b,X5=a，根据P的产生式集，可以

17、构造出如下的三角型：3.4上下文无关语言识别算法构造过程如下：P见前面定义。1、构造出第一行，即ω11，ω21，ω31，ω41和ω51，它们分别可由P中的对应式子取出，这些式子即是左边为非终极符，右边为终极符。此时k=0。根据P的集合，可以得到：ω11={B}ω21={A,C}ω31={A,C}ω41={B}ω51={A,C}3.4上下文无关语言识别算法2、构造第二行，即ω12，ω22，ω32，ω42，此时k可能的取值情况仅为1，则根据以下的计算式来计算各值：ω12=ω11+ω21={B}{A,C}={BA,BC}={A,S}ω22=ω21+ω

18、31={A,C}{A,C}={AA,AC,CA,CC}={B}3.4上下文无关语言识别算法ω32=ω31+ω41={A,C}{B}={AB,CB}={S,C}ω42=ω41+ω51={B}{A,C}={BA,BC}={S,A}3.4上下文无关语言识别算法3、构造第三行，即ω13，ω23，ω33，此时k可能的取值情况为1或2，也就是说，对于长度为3的串，可以将其分为1＋2，也可以将其分为2＋1，有：ω13=(ω11+ω22)∪(ω12+ω31)={B}{B}∪{A,S}{A,C}={Φ}∪{AA,AC,SA,SC}={Φ}3.4上下文无关语言识别

19、算法ω23=(ω21+ω32)∪(ω22+ω41)={A,C}{S,C}∪{B}{B}={AS,AC,CS,CC}∪{Φ}={B}3.4上下文无关语言识别算法ω33=(ω31+ω42)∪(ω32+ω51)={A,C}{S,A}∪{S,C}{A,C}={Φ}∪{B}={B}3.4上下文无关语言识别算法4、同理，可以构造第四行ω14，ω24，k分别取1,2,3，即分为1+3,2+2,3+1三种情况：ω14=(ω11+ω23)∪(ω12+ω32)∪(ω13+ω41)={B}{B}∪{A,S}{S,C}∪{Φ}{B}={Φ}3.4上下文无关语言识别算法

20、ω24=(ω21+ω33)∪(ω22+ω42)∪(ω23+ω51)={A,C}{B}∪{B}{S,A}∪{B}{A,C}={A,C,S}3.4上下文无