哈工大形式语言与自动机课件第三讲

形式语⾔及⾃动机哈尔滨⼯业⼤学（中⽂版）4PDA与CFG的等价性4.1由CFG到PDA定理5.如果L是上下⽂⽆关语⾔,那么存在PDA P,使L=N(P).证明.构造PDA:设CFG G=(V,T,P′,S)且L(G)=L,构造PDAP=({q},T,V∪T,δ,q,S,?)其中δ定义:(1)对每个变元A:δ(q,ε,A)={(q,β)|A→β∈P′}(2)对每个终结符a:δ(q,a,a)={(q,ε)}那么P可以模拟G的最左派⽣,每个动作只根据栈顶的符号:如果是终结符则与输⼊串匹配,如果是⾮终结符⽤产⽣式来替换.充分性:要证明S??w=?(q,w,S)?*(q,ε,ε).那么任意w∈L(G),则存在最左派⽣S??lm w,并且除最后⼀步派⽣的w外,每次派⽣的最左句型都有xAα的形式,这⾥x∈T?,A∈V,α∈(V∪T)?.S=x1A1α1?lm x2A2α2?lm···?lm x n?1A n?1αn?1?lm x nαn=ww=x1y1=x2y2=···=x n?1y n?1=x n y n=w (q,w,S)=(q,y1,A1α1)?*(q,y2,A2α2)?*···?*(q,y n?1,A n?1αn?1)?*(q,y n,αn)=(q,ε,ε)当处于S??lmw的第i步时,若x i y i=w,有:x i A iαi??lm x i+1A i+1αi+1=?(q,y i,A iαi)?*(q,y i+1,A i+1αi+1)因为,当最左派⽣处于左句型x i A iαi时,ID为(q,y i,A iαi),如果有A i→β的产⽣式,则x i A iαi?lm x iβαi⽽x iβαi也是左句型,所以最左的变量即为A i+1,则A i+1之前x i之后的终结符记为x′,A i+1之后的记为αi+1,那么就有x i A iαi?lm x iβαi=x i x′A i+1αi+1那么由(1)P模拟A i→β的动作得到(q,y i,A iαi)?(q,y i,βαi)=(q,y i,x′A i+1αi+1)由(2)P会弹出x′,⽽y i会去掉与x′匹配的前缀,剩下的部分记为y i+1(即y i=x′y i+1),那么(q,y i,x′A i+1αi+1)?*(q,y i+1,A i+1αi+1)因此当S??lmw有(q,w,S)?*(q,ε,ε),即L(G)?N(P).必要性:要证明(q,w,S)?*(q,ε,ε)=?S??w.我们证明更⼀般的结论(q,x,A)?*(q,ε,ε)=?A??x.通过对ID转移的次数进⾏归纳证明.归纳基础:当仅需要1次时,只能是x=ε且A→ε为产⽣式.(因为即使x=a和产⽣式A→a,也需要2步才能清空栈:替换栈顶A为a,再弹出a.)所以A??ε成⽴.归纳递推:假设转移次数不⼤于n(n≥0)步时结论成⽴.当需要n+1步时,因为A是变元,其第1步转移⼀定是(q,x,A)?(q,x,Y1Y2···Y m)且A→Y1Y2···Y m是产⽣式,其中Y i是变元或终结符.⽽其余的n步转移(q,x,Y1Y2···Y m)?*(q,ε,ε)中,每个Y i不论是变元或终结符,从栈中被完全弹出时,都会消耗掉部分的x,记为x i,那么显然有x=x1x2···x m.⽽且为了清空每个Y i,需要的转移次数都不超过n,所以对i=1,2,···,m有(q,x i,Y i)?*(q,ε,ε)=?Y i??x i.再由A的产⽣式有Y1Y2···Y m??lm x1Y2···Y m??lm x1x2···Y m??lm x1x2···x m=x.A?lm因此(q,w,S)?*(q,ε,ε)=?S??w,即N(G)?L(G).⽰例为⽂法S→aAA,A→aS|bS|a构造PDA.构造PDA P=({q},{a,b},{a,b,A,S},δ,q,S,?),其中δ为δ(q,ε,S)={(q,aAA)}δ(q,a,a)={(q,ε)}δ(q,ε,A)={(q,aS),(q,bS),(q,a)}δ(q,b,b)={(q,ε)}.利⽤GNF的构造⽅法将⽂法转换为GNF格式的CFG G=(V,T,P′,S),那么PDA P的另⼀种构造⽅式为:P=({q},V,T,δ,q,S,?)为每个产⽣式,定义δ:δ(q,a,A)={(q,β)|A→aβ∈P′}.⽰例上例中的⽂法是GNF,构造PDA P′=({q},{a,b},{S,A},δ,q,S,?),其中δ为δ(q,a,S)={(q,AA)}δ(q,a,A)={(q,S),(q,ε)}δ(q,b,A)={(q,S)}.4.2由PDA到CFG定理6.如果PDA P,有L=N(P),那么L是上下⽂⽆关语⾔.证明.⽂法构造:设PDA P=(Q,Σ,Γ,δ,q0,Z0,?).那么构造CFG G=(V,T,P,S),其中V是形如[qXp]的对象和符号S的集合,其中p,q∈Q,X∈Γ,产⽣式集合P包括:(1)为Q中的每个p,构造⼀个产⽣式:S→[q0Z0p](2)如果δ(q,a,X)包括(p,Y1Y2···Y n),构造⼀组产⽣式:[qXr n]→a[pY1r1][r1Y2r2]···[r n?1Y n r n]这⾥a∈Σ∪{ε};X,Y i∈Γ;p,q∈Q;⽽r1,r2,···r n是Q中各种可能的n个状态;若i=0则构造产⽣式[qXp]→a.那么(q,w,X)?*(p,ε,ε)??[qXp]??w.充分性:ID序列(q,w,X)?*(p,ε,ε)表⽰栈弹出X⽽消耗了串w(状态从q到了p);⽽[qXp]??w 表⽰在P中经过栈符号X可以产⽣出w(状态从q到了p);设w=ax,a∈Σ∪{ε}.(1)我们要证明(q,w,X)?*(p,ε,ε)=?[qXp]??w(2)左边部分ID动作变化如果需多步完成,那么第1步时,⼀定有δ(q,a,X)包含(p,Y1Y2···Y n),(i)则第1步为(q,ax,X)?(p,x,Y1Y2···Y n)⽽其余步骤中,为弹出Y i会消耗x中的⼀部分x i,显然w=ax=ax1x2···x n;(ii)设弹出Y i之前和之后(弹出Y i+1之前)的状态分别是r i?1和r i,消耗的串是x i,这⾥i=1,2,···n且r0=p,那么其他步骤就是(r i?1,x i,Y i)?*(r i,ε,ε)(iii)⽽根据⽂法的构造规则,有[qXp]?a[pY1r1][r1Y2r2]···[r n?1Y n r n](iv)因此,只要i=1,2,···,n有(r i?1,x i,Y i)?*(r i,ε,ε)=?[r i?1Y i r i]??x i成⽴,就有[qXp]?a[pY1r1][r1Y2r2]···[r n?1Y n r n]??ax1x2···x n=w成⽴.(3)⽽左边部分ID动作变化如果仅需1步完成(或者说i=0时),由于(q,a,X)?(p,ε,ε),P只能消耗不超过⼀个的字符,即w=a(a∈Σ∪{ε}),且(p,ε)在δ(q,a,X),所以,由⽂法构造规则[qXp]→a,即(q,a,X)?(p,ε,ε)=?[qXp]?a因此(q,w,X)?*(p,ε,ε)=?[qXp]??w.必要性:略.⽰例将PDA P=({p,q},(0,1),{X,Z},δ,q,Z)转为CFG,其中δ如下:(1)δ(q,1,Z)={(q,XZ)}(4)δ(q,ε,Z)={(q,ε)}(2)δ(q,1,X)={(q,XX)}(5)δ(p,1,X)={(p,ε)}(3)δ(q,0,X)={(p,X)}(6)δ(p,0,Z)={(q,Z)}0S →[qZq ]S →[qZp ]消掉[qZp ],因与⾃⼰循环1[qZq ]→1[qXq ][qZq ][qZq ]→1[qXp ][pZq ][qZp ]→1[qXq ][qZp ]...[qZp ]→1[qXp ][pZp ]因⽣成step 2中的[qZp ]······5确定型下推⾃动机(DPDA)PDA P =(Q,Σ,Γ,δ,q 0,Z 0,F )是确定型下推⾃动机(DPDA ),当且仅当:(1)δ(q,a,X )⾄多有⼀个动作,这⾥a ∈Σ∪{ε};(2)如果δ(q,a,X )=?,那么δ(q,ε,X )=?.即?(q,a,Z )∈Q ×Σ×Γ,|δ(q,a,Z )|+|δ(q,ε,Z )|≤1.在任何情况下都不需要去选择可能的移动就是DPDA,以终态⽅式接受的语⾔也称为DCFL.虽然与PDA 不等价,但也有意义,例如语法分析器通常都是DPDA,DPDA 接受的语⾔是⾮固有歧义语⾔的真⼦集,Knuth 提出LR(k )⽂法的语⾔也恰好是DPDA 接受语⾔的⼀个⼦集,解析的时间复杂度为O (n ),LR(k )⽂法也是YACC 的基础.任何DPDA 都⽆法接受L wwr ,但是可以接受L wcwr ={wcw R|w ∈(0+1)?}.0,Z 0/0Z 01,0/101,Z 0/1Z 00,1/010,0,0/ε5.1RL 与DPDA定理7.如果语⾔L 是正则的,那么有DPDA P ,使L =L (P ).(注意是以终态⽅式接受.)DPDA P 可以不使⽤栈,⽽仅模拟DFA 即可.⼜因为L wcwr 显然是CFL,所以L (P )语⾔类真包含正则语⾔.5.2DPDA 与CFLDPDA P ⽆法识别L wwr .所以L (P )语⾔类真包含于上下⽂⽆关语⾔.5.3DPDA 与歧义⽂法定理8.如果有DPDA P ,语⾔L =L (P ),那么L 有⽆歧义的CFG.定理9.如果有DPDA P ,语⾔L =N (P ),那么L 有⽆歧义的CFG.证明略.DPDA也因此在语法分析中占重要地位.但是并⾮所有⾮固有歧义CFL都会被DPDA 识别.例如L wwr有⽆歧义⽂法S→0S0|1S1|ε.5.4语⾔间的关系a nb nc nww Rwcw Ra?b?。

形式语言及自动机哈尔滨工业大学（中文版）1正则表达式(Regular Expression)自动机通过识别来定义语言，正则表达式通过规则产生语言(或表示语言)；正则表达式，所表示的语言与正则语言等价。

1.1语言的运算如果L和M是两个语言:1)L∪M为两个语言的并2)LM为两个语言的连接3)L?为语言的(克林)闭包示例四则运算表达式的定义1)任何的数都是四则运算表达式;2)如果a和b是四则运算表达式，那么a+b,a?b,a×b,a÷b和(a)都是四则运算表达式.1.2正则表达式的递归定义设Σ为字母表，则Σ上的正则表达式，递归定义为:1)?是一个正则表达式，表示空语言;2)ε是一个正则表达式，表示语言{ε};3)Σ中的任意字符a，都是一个正则表达式，分别表示语言{a};4)如果正则表达式r和s分别表示语言R和S，则r+s,rs,r?和(r)也是正则表达式，分别表示语言R∪S,RS,R?和R.示例00表示语言{00}.(0+1)?表示任意0和1构成的串.(0+1)?00(0+1)?表示至少有两个连续的0的串. (0+ε)(1+10)?表示没有两个连续0的串.1.3运算符的优先级正则表达式的三种运算：“加”(+)、“连接”(·一般省略)和“星”(?).正则表达式中运算符的优先级:括号的优先级最高，但括号本身并不是运算1)首先，“星”优先级最高:r?2)其次，“连接”:rs,r·s3)最后，“加”优先级最低:r+s示例01?+1=(0(1?))+12有穷自动机和正则表达式2.1正则语言的表示2.2DF A ?RE,递归构造R (k )ij定理:如果L =L (A )是某个DFA A 的语言，则有一个正则表达式R ，且L =L (R ).设DFA A 的状态共有n 个，若为每个结点编号，DFA A 的状态可表示为{1,2,...,n }。

正则表达式R (k )ij表示，在结点i 到j 的全部路径中，路径所经过的结点不超过k 的全部路径的正则表达式集合，但不包括起点i 和终点j 。