第02章 形式语言与自动机理论

第二章形式语言与自动机理论基础主要内容：语言和文法有限自动机正则表达式语言和文法语言和文法的关系什么是语言？如何表述语言？什么是程序设计语言？如何表述程序设计语言？语言和文法基本概念字母表：元素的非空有穷集合。

符号串：由字母表中的符号组成的任何有穷序列。

或者如下定义：

1.空符号串ε是

上的符号串

2.若x是

上的符号串,a是

的元素,则xa是

上的符号串

3.

y是

上的符号串,当且仅当它可以由1和2导出

思考如下问题：

1.符号串的长度如何定义？

2.{ε}和有何区别？

3.如何判断两个符号串相等？符号串的连接：设x和y均是字母表∑上的符号串，它们的连接是把y的所有符号顺序接在x的符号之后所得到的符号串。

符号串的方幂：设x是字母表∑上的符号串，把x自身连接n次得到的符号串z,称作符号串x的n次幂，记作z=xn

，特别地：x0=

前缀和后缀：设x是字母表上的符号串，x=yz,则y是x的前缀，z是x的后缀，特别是当z≠时，y是x的真前缀；y≠ε时，z是x的真后缀。子字符串：非空字符串x,删去它的前缀和后缀后所得到的字符串称为x的子字符串，简称子串。如果删去的前缀和后缀不同时为ε,则称该子串为真子串。语言和文法符号串集合：若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。符号串集合的乘积：设A、B是两个符号串集合，AB表示A与B的乘积，则定义

AB={xy|(x∈A)∧(y∈B)}

符号串集合的方幂：设A是符号串集合，则称Ai

是符号串集合A的方幂，其中i

是非负整数。

A0={},A1=A,A2=AA,…,An=AA…A符号串集合的正闭包：A+=A1∪A2∪A3…

符号串集合的星闭包：A*=A0∪A1∪A2∪A3…语言和文法文法之概述文法能清晰地描述程序设计语言的语法构成易于理解。文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。基于文法实现的语言易于扩展语言和文法文法之定义文法G定义为四元组(VT,VN,S,P)VT是有限的终极符集合

VN是有限的非终极符集合

S是开始符，S

VNP是产生式的集合，且具有下面的形式：

，其中，

(VT

VN)*语言和文法文法之分类O型文法:

也称为短语文法，其产生式具有形式:

→

，其中

,

(VT

VN)*，并且

至少含一个非终极符。1型文法:

也称为上下文相关文法。它是0型文法的特例，要求|

|

|

|(S→

例外，但S不得出现于产生式右部)。2型文法:

也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符:A→

。3型文法:

也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一:A→a，A→aB

其中A,B

VN

，a

VT

。

语言和文法上下文无关文法（CFG）定义为四元组(VT,VN,S,P)VT是有限的终极符集合

VN是有限的非终极符集合

S是开始符，S

VNP是产生式的集合，且具有下面的形式：

AX1X2…Xn

其中A

VN，Xi

(VT

VN)，右部可空。语言和文法文法相关概念推导（直接推导）：如果A

是一个产生式，则有A,其中表示一步推导(用A→)。这时称是由A直接推导的。的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。

+:

表示通过一步或多步可推导出

*:

表示通过0步或多步可推导出语言和文法句型：如果有S

*

，则称符号串

为CFG的句型。我们用SF(G)表示文法G的所有句型的集合。句子：如果

只包含终极符，则称

为CFG的句子。语言：

L(G)={u|S

+u,u

VT*}

文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。

最左（右）推导：如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号

lm（

rm）表示最左（右）推导。左（右）句型：用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。结论：每个句子都有相应的最右和最左推导（但对句型此结论不成立）短语：设S是文法的开始符，

是句型(即有S

*

），如果满足条件：

S

*

A

A

+

则称

是句型

的一个短语。直接短语（简单短语）：如果满足条件：

S

*

A

A

则称

是句型

的一个简单短语。句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。语言和文法语法分析树(简称分析树)用来描述句型的结构，是句型推导的一种树型表示。文法G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵分析树：

1.每个结点都有G的一个文法符号，并且根结点标有初始符S，非叶结点标有非终极符，叶结点标有终极符或非终极符或

。

2.如果一个非叶结点A有n个儿子结点(从左到右）为

X1,X2,...,Xn，则G一定有产生式

A→X1X2...Xn

。线性推导：我们称用

符号进行的推导为线性推导。树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树(如果无二义性)，而线性推导则可很多。语言和文法二义性文法：如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。文法G=({+,*,I,(,)},{E},E,P),其中P为：

EiEE+EEE*EE(E)句型i*i+i:推导1:EE+EE*E+Ei*E+Ei*i+Ei*i+i推导1:EE*E

i*Ei*E+Ei*i+Ei*i+i推导1的语法树E+EEE*EiiiEE*EE+Eii推导2的语法树i语言和文法文法等价变换增加拓广产生式

定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。

证明：假设S是G1的开始符，则只要在G1中扩充一条新产生式Z

S即可，其中Z是新的开始符。另这样扩充后的文法为G2，则它显然满足定理的要求。

消除空产生式

定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。

证明：根据G1，构造G2的方法如下：

(1)令

={A|A

} (2)

=

{A|A

+

,

+}。

(3)从G1中删除所有空产生式。

(4)从G1中删除只能导出空串的非终极符。

(5)对于文法中任意产生式A

X1X2…Xi-1XiXi+1…Xn a.若Xi

VT，不做动作；

b.若Xi

VN-

，不做动作；

c.若Xi

，补充规则A

X1X2…Xi-1Xi+1…Xn； 例：AaBcD

Bb|DBB|d消除不可达产生式

定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。

证明：根据G1，构造文法G2的方法如下：

(1)令

={Z|Z是文法的开始符}。

(2)递归扩充

直到收敛为止，即

=

{B|A

xBy

G1,B

VN,A

} (3)若一个产生式左部非终极符A

，则删除以A为左部的所有产生式。消除特型产生式

定理：对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，且在G2中没有特型产生式。 证明：构造无特型产生式的文法G2的方法如下：

(1)对文法G1中任意非终极符A，求集合

A={B|A

+B,B

VN}。

(2)若B

A，且B

是文法G中的一个非特型产生式，则补充如下规则A

。

(3)去掉文法G1中的所有的特型产生式。

(4)去掉新的文法中的无用产生式。 例： AB|D|aB BC|b

Cc DB|d消除文法二义性

S

ifEthenS |ifEthenSelseS |Other

该文法是一个二义性文法，与之等价的无二义性的文法如下：

S

M|U M

ifEthenMelseM |Other U

ifEthenS |ifEthenMelseU消除公共前缀

某个非终极符A有如下的两个产生式：

A→

，A→

(即有左公共前缀)

消除方法：

1.产生式形如：A

1|2|…|n|

表示不以

开头的字符串。

2.引进非终极符A’，使产生式替换为：

AA| A1|2|…|n消除左递归

一个文法含有下列形式的产生式时

（1）A

Aa

|b

AVN,a,(VNVT)*

（2）

AB| BA|bA,BVN,a,,(VNVT)*

其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有A

+A…，则称文法为左递归的。

（1）对直接左递归形如：

AA|

消除左递归：

AA AA|

（2）间接左递归形如：

AB| BA|b

消除左递归：转为直接左递归形式：

AA|b|或者

BB||b

按照直接左递归方式消除。去掉多余的产生式。有限自动机主要内容：确定有限自动机DFA(DeterninisticFA)非确定有限自动机NFA(NondeterninisticFA)NFA到DFA的转换DFA的化简确定有限自动机定义确定有限自动机DFA为一个五元组(,S,S0,f,Z)，其中：确定有限自动机是有穷字母表，每个元素称为一个输入字符；S是一个有穷集，它的每个元素称为一个状态；S0

S是唯一的一个初始状态；f是在SS上的转换函数（单值）；ZSS，是终止状态集，又称为接受状态集；一个DFA的例子

DFAM=({a,b},{S,U,V,Q},f,S,{Q})，其中f定义为：

f(S,a)=U f(V,a)=U f(S,b)=V f(V,b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,b)=Q确定有限自动机DFA的两种表示方式

状态转换图结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。

状态转换矩阵可用二维数组描述。标识出初始状态和终止状态。若DFA中有f(SI,a)=SJ，则：

Trans(SI，a)＝

SJ确定有限自动机对于

*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）。DFAM所能接受的字符串的全体记为L(M)

称为M所能接受（识别）的语言。确定有限自动机DFA接受的字符串初始状态唯一。转换函数f:SS是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(s,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。没有空边。即没有输入为（）确定有限自动机DFA的确定性非确定有限自动机是字母表

SS是状态集

S0是初始状态集

f是转换函数，但不要求是单值的

f:SS(∪{

})

2SSTS是终止状态集非确定有限自动机及相关概念

定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中

非确定有限自动机定义2：设A是一个NFA，A=(,SS,S0,f,TS)

则定义L(A)为从任意初始状态到任意终止状态所接受的字符串集合。

L(A)={|s0

s’,s0

S0

s’TS}NFA的一个例子SPZ00,1111自动机等价 设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。NFA到DFA的转换（确定化） 对于每一个非确定自动机A，存在一个确定自动机A’，使得L(A)=L(A’)。非确定有限自动机确定化算法—子集法

已知NFA:A=(

,S,f,S0,Z)

构造DFA:A’=(

,S’,f’,S0’,Z’) 1.令A’的初始状态为S0’=[S1,S2,…Sk],

其中S1…Sk是A的全部初始状态。

2.若S’=[S1,…,Sm]是A’的一个状态，a

则定义

f’(S’,a)=f(S1,a)

f(S2,a)…

f(Sm,a)=Q

将Q加入S’，重复该过程，直到S’收敛。

3.若S’=[S1,…,Sn]是A’的一个状态,且存在一个Si是A的终止状态，则令S’为A’的终止状态。非确定有限自动机带空边的NFA的确定化

定义：设I是NFA的状态集的子集，则I的闭包为：

_CLOSURE(I)=

I{q|f(p,)=q,p_CLOSURE(I)}

定义：设I是NFA状态集的子集，则

Ia=_CLOSURE(J)，J={q|f(p,a)=q,pI}非确定有限自动机确定化算法—子集法

已知A：NFA,构造A’:DFA 1.令A’的初始状态为

I0’=_CLOSURE({S1,S2,…Sk}),

其中S1…Sk是A的全部初始状态。

2.若I={S1,…,Sm}是A’的一个状态，a

则定义

f’(I,a)=Ia

将Ia加入S’，重复该过程，直到S’收敛。

3.若I’={S1,…,Sn}是A’的一个状态,且存在一个Si是A的终止状态，则令I’为A’的终止状态。非确定有限自动机带空边的NFA确定化的例子非确定有限自动机DFA化简（极小化）

状态等价对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。无关状态

从有限自动机的开始状态开始，任何输入序列都不能到达的状态。最小DFA

如果DFA中没有无关状态，也没有彼此等价的状态，则称该自动机是最小的。非确定有限自动机DFA化简算法--状态分离法

1.将DFA的所有状态K按终态和非终态划分成两个子集Z与K-Z，构成初始化分，记作：

={Z,K-Z}。

2.设当前的划分中已经含有m个子集:={I1,I2,…,Im}

对于每一个子集Ii={Si1,Si2,…,Sin}及每一个a，设

Iin=f(Ii,a)=f(Si1,a)f(Si2,a)……f(Sin,a)

若Iin中的状态分别落在中p个不同的子集，则将Iin分为p个更小的子集，得到新的划分new。

3.

若new,则将new作为重复(2)，直到不能划分。

4.将最后所得到的划分中的每个子集看成一个状态，边作相应修改，确定开始状态和结束状态。非确定有限自动机DFA化简的例子非确定有限自动机DFA化简的例子非确定有限自动机

aCDBAEFSbaaaaabbbbbabF正则表达式描述程序设计语言中单词的一种简单而且数学化的工具。表示符号串的构成模式正则表达式r定义了一个符号串集合rs,rs内的每个符号串都与r所定义的模式相匹配，rs称为由r生成的语言L(r)正则表达式中出现的所有符号构成的集合为该正则表达式的字母表，用S表示

正则表达式主要内容：基本概念正则表达式定义及一些性质扩充的正则表达式及程序设计语言中单词的定义正则表达式与有限自动机等价正则表达式正则表达式定义为给定的字母表，则每个上的正则表达式将定义上的一个字符串集。用R

表示上的正则表达式，用L(R

)表示R

所表示的字符串集合。即：函数L表示正则表达式到字符串集的映射。则R

的定义及其含义如下：

是正则表达式，即

R

。其中L(

)={}。

是正则表达式，即

R

。其中L(

)={

}。

c

是正则表达式，即c

R

。其中L(c)={c}。

A和B是正则表达式，即A

R

，B

R

，则有

(A)

R

， L((A)) =L(A) A|B

R

， L(A|B) =L(A)

L(B) AB

R

， L(AB) =L(A)L(B) A*

R

， L(A*) =L(A)*

正则表达式正则表达式例

={a,b}.

正则表达式eab*2.a(a|b)*

L(e)

上所有以a为首后跟任意多个（包括0个）b的字符串集上所有以a为首的字符串集正则表达式正则表达式的性质

A|B=B|A |的可交换性

A|(B|C)=(A|B)C |的可结合性

A(BC)=(AB)C 连接的可结合性

A(B|C)=AB|AC 连接的可分配性

(A|B)C=AC|BC连接的可分配性

A**=A*

幂的等价性

Al=lA=A

l是连接的恒等元素

正则表达式

扩充的正则表达式

一次或多次重复:A+

任何符号:“.”在字母表中任何符号.

符号范围:[0--9][a--z][A--Z]

不在给定范围内的符号:[^

a]

可选:（＋|-）?