形式语言与自动机理论(一)

形式语言与自动机理论2010年3月1参考教材1、形式语言与自动机理论

作者：蒋宗礼、姜守旭

出版社：清华大学出版社

2、AnIntroductiontoFormalLanguagesandAutomata(ThirdEdition)

作者：PeterLinz出版社：机械工业出版社3、IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)

作者：JohnE.Hopcroft,RajeevMotwani,JeffreyD.Ullman出版社：清华大学出版社2第一章绪论计算机科学研究的课题是：可计算性；算法和复杂性理论；数据结构和数据库；人工智能；人机交互和人机界面。

3第一章绪论计算机科学理论计算机科学①自动机论与形式语言理论；②程序理论（包括程序正确性证明、程序验证等）；③形式语义学；④算法分析和计算复杂性理论。实验计算机科学4第一章绪论1.4语言1.4.1语言的非形式和形式定义Webster定义：为相当大的团体的人所懂得,并使的字和组合这些字的方法的统一体。5第一章绪论1.4语言1.4.1语言的非形式和形式定义吴天蔚定义：语言可以被看成一个抽象的数学系统。（1994）(信息产业部计算机与微电子发展研究中心)Chomsky定义：按照一定规律构成的句子和符号串的有限或无限的集合。6第一章绪论1.4语言1.4.2形式语言和自动机理论的产生和作用

（1）产生过程

形式语言的产生过程

自动机的产生过程（2）作用7第一章绪论1.4语言1.4.3基本概念形式语言的直观意义形式语言是用来精确描述语言（包括人工语言和自然语言）及其结构的手段。形式语言学也称代数语言学。8第一章绪论1.4语言1.4.3基本概念对语言研究的主要方面：（2）有穷描述（1）表示（3）语言的结构9第一章绪论语言描述的三种途径：（1）穷举法：只适合句子数目有效的语言。（2）语法描述：生成语言中合格的句子。（3）自动机：对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子。1.4语言1.4.3基本概念10第一章绪论1.4语言1.4.3基本概念（1）符号（2）字母表（3）字符串（4）语言字母表的运算①乘积运算②幂运算③闭包运算11第二章文法2.1文法的引入例1汉语中的句子：王平和李新是大学生。它由两个短语组成：〈主语〉 〈谓语〉王平和李新 是大学生

该句子可以应用下列规则构成：12第二章文法1．〈句子〉→〈主语〉〈谓语〉2．〈主语〉→〈名词短语〉3．〈名词短语〉→〈名词〉4．〈名词短语〉→〈名词〉〈连接词〉〈名词短语〉5.〈名词〉→王平6.〈名词〉→李新7.〈连词〉→和8.〈谓语〉→〈动宾短语〉9．〈动宾短语〉→〈动词〉〈宾语〉10.〈动词〉→是11.〈宾语〉→〈名词〉12.〈名词〉→大学生

13第二章文法该文法也能产生:王平是大学生；李新和王平是大学生；王平和大学生是李新；王平和王平和王平是王平等句子。

14第二章文法2.2文法的形式定义2.2.1定义

文法G是一个4元组G=(V,T,P,S)

其中：（1）V是非终结符非空有限集合；（2）T是终结符的非空有限集合；

并且VÇT=F；（3）P是产生式的非空有限集合；（4）SÎV是文法G的开始符。15第二章文法2.2文法的形式定义2.2.2推导和归约定义：假设G=(V,T,P,S)是一个文法。如果a®bP,并且,(VT）*，则称a直接推导出b，记为：ab

如果ab，则称b在文法G中直接归约成a，简称为归约。16第二章文法2.2文法的形式定义2.2.3语言定义：设文法G=(V,T,P,S)。对(VT)*，如果S()*,

则为文法G的一个句型；若对wT*，如果S()*w，则w

称为由G产生的一个句子。称L(G)={w|wT*,

S()*w}为文法G产生的语言。17第二章文法2.3文法的构造例1：构造文法G，使

L(G)={0,1,00,11}定义：假设G1,G2是文法，如果

L(G1)=L(G2)，则称G1,G2是等价的。18第二章文法2.3文法的构造例2：构造文法G，使(1)L(G)={0n|n0}(2)L(G)={0n|n1}(3)L(G)={0n1n|n0}(4)L(G)={0n1n|n1}(5)L(G)={0n1n+1|n0}(6)L(G)={0n1n2n|n1}19第二章文法2.4文法的类型2.4.1Chomsky体系(1)0型文法(短语结构文法)

对产生式不做任何限制PSG(phrasestructuregrammar)PSL(phrasestructurelanguage)

RE(recursivelyenumerable

)20第二章文法2.4文法的类型2.4.1Chomsky体系(2)1型文法（上下文有关文法）

对P,都有||||CSG(contextsensitivegrammar)CSL(contextsensitivelanguage)21第二章文法2.4文法的类型2.4.1Chomsky体系(3)2型文法（上下文无关文法）

对P,都有||||，并且VCFG(contextfreegrammar)CFL(contextfreelanguage)22第二章文法2.4文法的类型2.4.1Chomsky体系(4)3型文法（正规文法、正则文法）

对P,有以下形式：AwB,AworABw,Aw

其中A,BV,wT+

RG(regulargrammar)RL(regularlanguage)23第二章文法2.4文法的类型2.4.2正规文法和正规语言定理：L是RL的充分必要条件是存在一个文法，该文法产生语言L,并且产生式的形式是：AaB,AaorABa,Aa其中A,BV,aT.

24第二章文法2.4文法的类型2.5空语句定义：假设G=(V,T,P,S)是一个文法。如果S不出现在G的任何产生式的右部，则P{S}所形成的文法仍然是与G等价的相应类型的文法，所产生的语言是相应类型的语言。25第三章有限状态自动机3.1有限状态系统3.2有限状态自动机的形式定义（１）形式定义定义：有限状态自动机（finiteautomaton,FA）是一个五元组：Ｍ=(Q,,,q0,F)其中，Q：非空有限状态集合；

：有限输入字母表；

：状态转换函数；：QQ；（DFA）q0：q0Q,是Ｍ的初始状态；

F：FQ是Ｍ的终止状态集。26第三章有限状态自动机3.1有限状态系统3.2有限状态自动机的形式定义例如：假设DFAM=(Q,,,q0,F)。其中Q={q0,q1,q2,q3}，={a,b}，F={q3}27第三章有限状态自动机3.1有限状态系统3.2有限状态自动机的形式定义输入字符串时，转换函数为：其定义为：对(1)对，有(2)当时，28第三章有限状态自动机3.2有限状态自动机的形式定义（２）设计有限状态自动机例１：构造一台有限状态自动机，它能够识别所有由奇数个ａ和奇数个ｂ组成的字符串。

设计考虑有以下状态：（1）到此为止读入偶数个a和偶数个b;

（2）到此为止读入奇数个a和偶数个b;

（3）到此为止读入偶数个a和奇数个b;（4）到此为止读入奇数个a和奇数个b;29例２：设计一台有限状态自动机，识别含有00作为子串的所有{0,1}上的字符串组成的语言。设计考虑以下状态：（1）开始状态，什么都没有输入或者输入1；（2）接收到的符号是0；（3）接收到的符号是00；第三章有限状态自动机3.2有限状态自动机的形式定义（２）设计有限状态自动机30第三章有限状态自动机3.2有限状态自动机的形式定义（２）设计有限状态自动机例3：设计一个DFAM，它能识别所有能被3整除的十进制数。设计可以考虑有以下情况：（1）已输入的数字与上一余数之和被3除余0；

（2）已输入的数字与上一余数之和被3除余1；

（3）已输入的数字与上一余数之和被3除余2；31第三章有限状态自动机3.2有限状态自动机的形式定义（3）即时描述（瞬时描述、格局）

定义：设M=(Q,,,q0,F)是一个FA,

x,y*,(q0,x)=q。则

xqy称为M

的一个即时描述

(instantaneousdescription,ID)。32第三章有限状态自动机3.2有限状态自动机的形式定义（4）到达某状态的字符串集合

定义：设FA

M=(Q,,,q0,F)，对qQ能从开始状态到达所输入的字符串集合为：

set(q)={x|x*,并且(q0,x)=q}33第三章有限状态自动机3.2有限状态自动机的形式定义（5）有限状态自动机等价

假设M1,M2是FA，如果L(M1)=L(M2)，则M1与M2等价。34第三章有限状态自动机3.3非确定的有限自动机(NFA)（1）形式定义

定义：非确定有限自动机（non-deterministicfiniteautomaton,NFA）是一个五元组：Ｍ=(Q,,,q0,F)其中，Q、、q0、F的定义与在FA中的定义相同；

：状态转换函数，：Qp(Q)

即对(q,a)Q

(q,a)={p1,p2,…,pm}Q35第三章有限状态自动机3.3非确定的有限自动机(NFA)状态转换函数：Qp(Q)，对qQ①对*②对a,w*有③对PQ36第三章有限状态自动机3.3非确定的有限自动机(NFA)（1）形式定义非确定的有限自动机(NFAM)所接受的语言:37第三章有限状态自动机3.3非确定的有限自动机(NFA)例：设计一台NFA，使它能够接受0，1形成的字符串且该字符串的最后两位是01。设计分析可以考虑以下情况：（1）在初始状态下，无论输入1还是输入0都是一种不可接受的状态；（2）在初始状态下，输入0时，是一种可能接受的状态；（3）在可能接受的状态下，输入1时，是可接受的状态。38第三章有限状态自动机3.3非确定的有限自动机(NFA)（2）DFA和NFA的等价性

定理：设L(MN)是由NFAMN所接受的语言。则存在一个DFAMD，使得L(MD)=L(MN)。39第三章有限状态自动机（1）形式定义3.4有转换的有限状态自动机(-NFA)

定义：有转换的NFAM是一个五元组：Ｍ=(Q,,,q0,F)其中，Q、、q0、F的定义与NFA中的定义相同；

：状态转换函数,：Q({})p(Q)

即对(q,a)Q({})

(q,a)={p1,p2,…,pm}Q40第三章有限状态自动机3.4有转换的有限状态自动机(-NFA)（2）相关概念

闭包

假设有转换的NFAＭ=(Q,,,q0,F)，对qQ,q的闭包是指由状态q出发，经过有限段弧到达的状态以及q本身组成的状态集合。记为-CLOSURE(q)。若PQ,那么-CLOSURE(P)=41第三章有限状态自动机3.4有转换的有限状态自动机(-NFA)（2）相关概念

的定义对qQ,w*,a

①②其中：42第三章有限状态自动机3.4有转换的有限状态自动机(-NFA)（2）相关概念

的定义

③对RQ

有转换NFAM所接受的语言43第三章有限状态自动机3.4有转换的有限状态自动机(-NFA)（3）-NFA与NFA的等价性

定理：如果-NFAM所接受的语言为L(M),那么存在一个NFAM1，使得L(M1)=L(M)44第三章有限状态自动机3.5FA是正规语言的识别器由文法推导句子Sa1A1Sa1A1A1a2A2a1a2A2……..…………

An-2an-1An-1a1a2…an-1An-2

An-1ana1a2…an-1an自动机识别句子(q0,a1)=q1q0a1…an├a1q1a2…an(q1,a2)=q2├a1a2q2a3…an……..…………

(qn-1,an)=qn├a1a2a3…anqnqnF45第三章有限状态自动机3.5FA是正规语言的识别器定理：FA接受的语言是正规语言思路：假设一台DFAM,它所接受的语言是L(M),该语言能够被正规文法推出。定理：正规语言能够被FA所接受思路：假设L是由正规文法产生的语言,构造一台自动机FA能够接受它。46第三章有限状态自动机3.5FA是正规语言的识别器例1：假设RGG=({S,B},{0,1},P,S)

其中P={S0B,B0B|1S|0}

构造一台NFAM,使得L(M)=L(G)。例2：由例1的NFAM

构造一台DFAM1,使得

L(M1)=L(M)。例3：由例2的DFAM1

构造一个RGG,使得

L(G)=L(M1)。47第三章有限状态自动机3.6FA的一些变形(1)双向有限自动机确定的双向有限自动机（2DFA）2DFA是一个五元组Ｍ=(Q,,,q0,F)其中，Q,,q0,F的定义与DFA的定义一致

：QQ{L,R,S}48第三章有限状态自动机3.6FA的一些变形(1)双向有限自动机格局变化2DFA所接受的语言L(M)={w|w*,q0w├wp,pF}49第三章有限状态自动机3.6FA的一些变形(2)带输出的有限自动机Moor机一个Moor机为六元组M=(Q,,,,,q0)其中，Q,,,q0的含义与DFA的一致。

：为有限输出字母表

:为输出函数Q50第三章有限状态自动机3.6FA的一些变形Moor机例：用Moor机设计一台模4往返计数器。

51第三章有限状态自动机3.6FA的一些变形(2)带输出的有限自动机Mealy机一个Mealy机为六元组M=(Q,,,,,q0)其中，Q,,,,q0的含义与Moor机的一致。:为输出函数Q

52第三章有限状态自动机3.6FA的一些变形Mealy机例如：用Mealy机设计一台奇偶校验器。

53第三章有限状态自动机3.6FA的一些变形Moor机和Mealy机的等价性54第三章有限状态自动机3.6FA的一些变形(2)带输出的有限自动机Moor机和Mealy机的等价性定义：设M=(Q,,,,,q0)为一个Moor机，M’=(Q’,,’,,’,q0)为一个Mealy机，且b=(q0),若对于w*,都有

TM(w)=bTM’(w)则称Moor机与Mealy机等价，记为M~M’。55第三章有限状态自动机3.6FA的一些变形(2)带输出的有限自动机定理：对每个Moor机M1=(Q,,,,,q0)都存在一个Mealy机M2,使得M2

~

M1.定理：对每个Mealy机M1=(Q,,,,,q0)都存在一个Moor机M2,使得M2

~

M1.56第三章有限状态自动机例1：构造与Moor机描述的模4往返计数器等价的Mealy机。57第三章有限状态自动机例2：给定一台Mealy机（如图所示），构造一台与它等价的Moor机。

58第三章有限状态自动机总结：概念：文法分类（0、1、2、3型文法）

自动机分类（DFANFA-NFA

2DFAMoorMealy）自动机之间、与文法之间的等价转换Moor机Mealy机-NFANFADFARG2DFA59第四章正规表达式4.1正规表达式的形式定义定义：设是一个字母表，字母表上正规式（RegularExpression,RE）和正规集定义如下：（1）是上的正规式，对应的正规集为；（2）是上的正规式，对应的正规集为{}；（3）对a，a是上的正规式，对应的正规集为{a}；60第四章正规表达式4.1正规表达式的形式定义（4）如果r和s分别是上的正规式，对应的正规集为R和S。那么(r+s)为正规式，对应的正规集为RS；(rs)为正规式，对应的正规集为RS；(r*)为正规式，对应的正规集为R*（5）只有满足上述形式定义的表达式才是上的正规式，它所表达的语言是正规集。61第四章正规表达式4.1正规表达式的形式定义例如：假设={a,b}(1)((a+b)*)(2)(ab*)(3)(b(a+b)*)(4)((a+b)*((aa)+(bb))(a+b)*)(5)（((((a*)b)a*)b)a*）62第四章正规表达式正规表达式的运算性质假设r,s,t都是上正规式，则有以下性质：（1）结合律；（2）分配律；（3）交换律；（4）幂等律；（5）加运算单位元；（6）乘运算单位元；（7）乘运算零元；（8）(r*)*=r*；（9）r*=r++；（10）*=（11）*=4.1正规表达式的形式定义63第四章正规