形式语言和自动机上下文无关文法与下推自动机课件

形式语言和自动机课件——上下文无关文法与下推自动机从上下文无关文法构造等价的下推自动机定理4.5.1（由CFG可导出PDA）：设上下文无关文法G＝（N，T，P，S），产生语言L（G），则存在PDAM，以空栈接受语言Lφ(M),使Lφ(M)=L(G)。

证明：构造下推自动机M，使M按文法G的最左推导方式工作。

2CollegeofComputerScience&Technology,BUPT构造方法设CFG

G=(N,

T,P

,S)

，构造一个空栈接受方式的PDAM＝（Q，T，Γ，δ，q0，z0，F）其中Q＝{q},Γ=N∪T,q0＝q，z0＝S,F＝φ(∵以空栈接受)即M=({q},T,NT,,q,S,F)

,

转移函数

定义如下：

(1)对每一AN,(q,,A)={(q,)"A”P};

（即将栈顶的A换为β）

(2)

对每一aT,(q,a,a)={(q,)}.（即若栈顶为终结符，则退栈）

从上下文无关文法构造等价的下推自动机3CollegeofComputerScience&Technology,BUPTqε，z0＝S/β若S→β∈P

ε，A/α若A→α∈P

a,a/εaT,

从上下文无关文法构造等价的下推自动机用图形表示：

例1对右边产生式所代表CFG，

依上述方法构造的PDA为EEOE(E)vdO＋

({q},{v,d,+,,(,)},{E,O,v,d,+,},,q,E,φ),其中定义为(q,,E)={(q,EOE),(q,(E)),(q,v),(q,d)},{(q,＋),(q,)},(q,,O)={(q,)},(q,v,v)=(q,d,d)=

{(q,)}(q,＋,＋)=(q,,)=(q,(,()=(q,),))=

4CollegeofComputerScience&Technology,BUPT自顶向下的分析过程定理的物理意义：利用下推自动机进行自顶向下的分析，检查一个句子的最左推导过程。步骤如下：

(1)初始时，将文法开始符号压入空栈.(2)如果栈为空，则分析完成.(3)如果栈顶为一非终结符，先将其从栈中弹出.选择下一个相应于该非终结符的产生式，并将其右部符号从右至左地一一入栈.如果没有可选的产生式，则转出错处理.(4)如果栈顶为一终结符，那么这个符号必须与当前输入符号相同，将其弹出栈，读下一符号，转第(2)步；否则，回溯到第(3)步.5CollegeofComputerScience&Technology,BUPT例2：利用下推自动机进行自顶向下的分析过程EEOE(E)vdO＋

EEOEEOvEOEEE)(E)E)OEE)OvE)OE)＋E))d)v(v＋d)qε，z0＝E/β若E→β∈P

ε，O/*a,a/εa∊{(,),v,d,+,*}

ε，O/+6CollegeofComputerScience&Technology,BUPT定理的证明证明思路欲证，对任何wT*,wL(G)wL(M).先证明如下结论,

if

Aw,

then

(q,w,A)├*(q,,).归纳于Aw的步数n.基础n=1，Aw必为产生式，(q,w,A)├(q,w,w)├*(q,,).归纳设第一步使用产生式AX1X2…Xm

，必有w=w1w2…wm

，

(q,w,A)├(q,w,X1X2…Xm

)├*(q,w2…wm,X2…Xm)├*(q,w3…wm,X3…Xm)├*…├*(q,,).所以:if

Sw,

then

(q,w,S)├*(q,,).即,

wL(G)wL(M).7CollegeofComputerScience&Technology,BUPT定理的证明先证明如下结论,

if

(q,w,A)├*(q,,),

thenAw.归纳于(q,w,A)├*(q,,)的步数n.归纳n>1，设第一步使用产生式AX1X2…Xm

，

可以将w

分为w=w

1w

2…w

m

，满足(q,wi,Xi)├*(q,,)，所以:对任何wT*,

if

(q,w,S)├*(q,,),

thenSw.

即,

wL(M)wL(G).因此，A

X1X2…Xm

，

w

1w

2…w

m

=w无论Xi为终结符，还是非终结符，都有Xi

w

i.基础n=1，必有w=，且A

为G

的产生式，所以A

w.8CollegeofComputerScience&Technology,BUPT例：构造一个PDAM，使Lφ(M)=L(G)。其中G是我们常用来生成算术表达式的文法：G＝（N，T，P，E）N＝{E,T,F},T={+,*,(,),a},S={E}P:E→E+T∣T;T→T*F∣F;F→(E)∣a解：构造M＝（{q}，T，Γ，δ，q，E，φ）

δ定义为：①δ(q,ε,E)＝{(q,E+T),(q,T)}②δ(q,ε,T)＝{(q,T*F),(q,F)}③δ(q,ε,F)＝{(q,(E)),(q,a)}④δ(q,b,b)＝{(q,ε)}对所有

b∈{a,+,*,(,)}例3:

从文法构造等价的下推自动机9CollegeofComputerScience&Technology,BUPT用格局说明句子分析过程例如以a+a*a作为输入，则M在所有可能移动中可作下列移动（用到文法G中从E出发的最左派生的一系列规则）（q，a＋a*a,E）├(q，a＋a*a,E+T)├(q，a＋a*a,T+T)├(q，a＋a*a,F+T)├(q，a＋a*a,a+T)├(q，＋a*a,+T)├(q，a*a,T)├(q，a*a,T*F)├(q，a*a,F*F)├……10CollegeofComputerScience&Technology,BUPT从下推自动机构造等价的上下文无关文法定理4.5.1是由G导出PDA，其逆定理也成立。

定理4.5.2（由PDA导出文法G）：设下推自动机M，以空栈形式接受语言Lφ(M），则存在一个上下文无关文法G，产生语言L(G),使L(G)=Lφ(M）。证明：设M＝（Q，T，Γ，δ，q0，z0，Φ）

思路：构造文法G，使ω串在G中的一个最左推导直接对应于PDAM在处理ω时所做的一系列移动。11CollegeofComputerScience&Technology,BUPT从下推自动机构造等价的上下文无关文法采用形如[q，z,γ]的非终结符,q，γ∈Q，z∈Γ[q，z,γ]的物理意义：在q状态，栈顶为z时，接受某个字符(可为ε)后PDA将变换到γ状态，并保证[q，z,γ]ω当且仅当（q,ω,z）├*（γ,ε,ε）.12CollegeofComputerScience&Technology,BUPT从下推自动机构造等价的上下文无关文法

构造方法

设PDAM＝（Q，T，Γ，δ，q0，z0，Φ）

,

构造CFGG＝（N,T,P,S）

其中N＝{[q,z,γ]│q,γ∈Q，z∈Γ}∪{S}产生式集合P

定义如下：对于每个q∈Q，将S→[q0，z0,q]加入到产生式中。

若δ（q，a，z）含有（γ,ε），则将[q,z,γ]→a加入到产生式中。若δ（q，a，z）含有（γ，B1,B2,…,Bk）k≥1，Bi∈Γ，则对Q中的每一个状态序列q1,q2,…,qk,(qi≤Q),把形如

[q,z,qk]→a[γ,B1,q1][q1,B2,q2]…[qk-1,Bk,qk]

的产生式加入到P中。其中，aT或a=

13CollegeofComputerScience&Technology,BUPT（书P169－170）由PDAM构造文法G设PDAM＝（{q0,q1},{a,b},{A,z0},δ,q0,z0,Φ）δ定义为：δ（q0,a,z0）={(q0,Az0)}①δ（q0,a,A）={(q0,AA)}②δ（q0,b,A）={(q1,ε)}③δ（q1,b,A）={(q1,ε)}④δ（q1,ε,A）={(q1,ε)}⑤δ（q1,ε,z0）={(q1,ε)}⑥例1:

从下推自动机构造等价的上下文无关文法14CollegeofComputerScience&Technology,BUPT

q0

b,A/ε

q1

a,z0/Az0

b,A/εa,A/AAε,A/ε

ε,z0/ε解：（1）∵q0,q1∈Q， ∴构造S→[q0,z0,q0];S→[q0,z0,q1]

（2）对③④⑤⑥式，可构造由δ（q0,b,A）={(q1,ε)}

得

[q0,A,q1]→b由δ（q1,b,A）={(q1,ε)}得[q1,A,q1]→b由δ（q1,ε,A）={(q1,ε)}得[q1,A,q1]→ε由δ（q1,ε,z0）={(q1,ε)}得[q1,z0,q1]→ε15CollegeofComputerScience&Technology,BUPT

q0

b,A/ε

q1

a,z0/Az0b,A/εa,A/AAε,A/εε,z0/ε（3）对①式δ（q0,a,z0）={(q0,Az0)}

，∵所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1∴可构造出产生式：

[q0,z0,q0]→a[q0,A,q0][q0,z0,q0][q0,z0,q0]→a[q0,A,q1][q1,z0,q0][q0,z0,q1]→a[q0,A,q0][q0,z0,q1][q0,z0,q1]→a[q0,A,q1][q1,z0,q1]16CollegeofComputerScience&Technology,BUPT

q0

b,A/ε

q1

a,z0/Az0b,A/ε

a,A/AA

ε,A/εε,z0/ε对②式δ（q0,a,A）={(q0,AA)}

，∵所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1∴可构造出产生式：

[q0,A,q0]→a[q0,A,q0][q0,A,q0][q0,A,q0]→a[q0,A,q1][q1,A,q0][q0,A,q1]→a[q0,A,q0][q0,A,q1][q0,A,q1]→a[q0,A,q1][q1,A,q1]17CollegeofComputerScience&Technology,BUPT(4)删除无用符号[q0,A,q1]和[q1,z0,q0]及相应产生式

重命名[q0,z0,q1]为AS→A[q1,A,q1]为BA→aCD[q0,A,q1]为C得B→b∣ε[q1,z0,q1]为DC→aCB∣bD→ε注:构造生成式时，可从S生成式出发，以避免生成无用产生式。18CollegeofComputerScience&Technology,BUPT定理的关键：当存在δ(q，a，z)含有（γ，B1B2…Bk）则对Q中的每个可能的状态序列q1q2…qk排成一条产生式[q,z,qk]→a[γ,B1,q1][q1,B2,q2]…[qk-1,Bk,qk]这是一个猜测过程，实质是写出从q出发，栈顶为Z，经过一系列推导走到qk的所有可能的状态序列，其中必有一条路径是正确的。

19CollegeofComputerScience&Technology,BUPTM＝（{q}，T，Γ，δ，q，E，φ）

δ定义为：①δ(q,ε,E)＝{(q,E+T),(q,T)}②δ(q,ε,T)＝{(q,T*F),(q,F)}③δ(q,ε,F)＝{(q,(E)),(q,a)}④δ(q,b,b)＝{(q,ε)}对所有

b∈{a,+,*,(,)}算术表达式的文法G＝（N，T，P，E）N＝{E,T,F},T={+,*,(,),a},S={E}P:E→E+T∣T;T→T*F∣F;F→(E)∣a练习：针对算术表达式的PDA反向构造其等价文法20CollegeofComputerScience&Technology,BUPT练习:

从PDA构造等价的上下文无关文法对于右下图的PDA，构造CFG

G=(N,{0,1},P,S)，

其中

N={S}{[p,Y,q]p,q{q0,q1,q2}Y{Z0,X}

}产生式集合P

定义如下：

(1)

S[q0,

Z0,

q0];S[q0,

Z0,

q1];S[q0,

Z0,

q2];

(5)由(q0,XZ0)(q0,0,Z0)得[q0

,Z0

,qj]0[q0

,X

,qi][qi

,Z0

,qj],i,j=0,1,2;

(6)由(q0,XX)(q0,0,X)得

[q0

,X

,qj]0[q0

,X

,qi][qi

,X

,qj],i,j=0,1,2;

(2)由(q1,)(q0,1,X)得[q0

,X

,q1]