形式语言与自动机课件全书教学教程电子教案幻灯片

12024/9/13

FormalLanguagesandAutomata形式语言与自动机

22024/9/13

绪论课程信息为什么学习形式语言与自动机形式语言与自动机概述及应用课程内容及要求32024/9/13

专业基础课

上世纪60年代末、70年代初，研究的高峰

之后，向应用领域渗透，研究生课程逐渐普及，本科阶段的专业基础课

专业工作者必须的理论素养

计算模型计算机（不）能够做什么问题分类计算的复杂性，算法分析形式系统建模工具（状态机

）抽象描述形式文法、形式表达式

课程性质42024/9/13

相关课程先修课程

《离散数学》（《数理逻辑》，《集合论》）计算机导论与程序设计、数据结构

后续课程

《编译原理》

其它相关课程《模式识别》、《算法分析》

52024/9/13

为什么学习形式语言与自动机形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。形式语言与自动机概述及应用本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。核心内容有限状态自动机，正规语言，正规表达式上下文无关文法，上下文无关语言，下推自动机图灵机，计算问题分类62024/9/13

72024/9/13

1．形式语言什么是形式语言形式语言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26个英文字母构成的字母表。字符串：字母表中的字符构成的有限序列。e.g.hello,afjhkfyu

82024/9/13

为什么用形式语言自然语言：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。形式语言通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之分。形式语言是某个字母表上的字符串的集合，有一定的描述范围。92024/9/13

例1：汉语：<主><谓><宾>――用数字、符号等形式化的东西来描述语言我吃饭――语法正确我饭吃――语法错误饭吃我――语法正确，语义错误102024/9/13

例2：T为PASCAL语言所用的全部符号的集合。正确的PASCAL程序就是T上的语言。例3：在字母表T={a}上，L={a2n+1|n>=0}表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）112024/9/13

形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。最初的应用：编译――让计算机按照语法规则将高级语言方便地翻译成机器语言。122024/9/13

现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域在计算机理论科学方面：是可计算理论（算法―在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。132024/9/13

2.自动机什么是自动机？具有离散输入输出的数学模型。大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。142024/9/13

自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”自动机的本质：根据状态、输入和规则决定下一个状态状态＋输入（激励）＋规则―>状态迁移152024/9/13

为什么叫自动机？可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。162024/9/13

例1：打电话(自动机在通信领域的应用)。

在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机收齐号码q0:空闲状态q1:等待拨号状态q2:可以拨号状态q3:等待应答状态q4:通话状态172024/9/13

例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q2182024/9/13

根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。基本图灵机由一个具有读写头的有限控制器和一条无限带组成。使用自动机，可以形式化的描述现实世界中的一些问题。192024/9/13

3．形式语言与自动机的关系形式语言和自动机是密切相关的。形式语言――字符串自动机――字符串的识别系统根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。202024/9/13

212024/9/13

语言与有限自动机（FiniteAutomata）设=0,1，L=w

w中至少有一个0，如0011,10,110111

L,而11,,1111

L。下图是一个可接受该语言的有限状态自动机222024/9/13

小结文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。232024/9/13

课程内容及要求课程内容：书上二、三、四、五章。要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，并能在实际中加以应用。通过对定理的证明，对同学们进行思维训练，并掌握一定的证明方法。第二章语言及文法主要内容：定义形式语言的术语给出文法的定义和文法的分类要求掌握：语言和文法的形式定义CHOMSKY文法体系的分类。242024/9/13

第一节语言的定义与运算一、语言的一些术语：

字母表：字符的有限集合，记为T。字符串：由字母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；

常用a,b,c,d

标识单个字符。252024/9/13

262024/9/13

字母表（Alphabet）

概念

形式符号的集合

记号常用T、

表示

举例英文字母表

a,b,…,z,A,B,…,Z

英文标点符号表,;:.?!’‘“”()…

汉字表…,自,…,动,…,机,…

化学元素表

H,He,Li,…,

T=a,n,y,…

272024/9/13

字符串（string）

概念字母表T上的一个字符串（简称串），或称为字（word），为T

中字符构成的一个有限序列。

空串（emptystring）,用

表示，不包含任何字符。举例设T=a,b，则

,

a,ba,bbaba等都是串

字符串w

的长度，记为

w

，是包含在w中字符的个数。

举例

=0，

bbaba

=5

ai

表示含有i个a的字符串

282024/9/13

连接（concatenation）

设x,y为串,且x

a1a2…am,y

b1b2…bn,则x与y的连接

xy

a1a2…amb1b2…bn

连接运算的性质

(xy)z

x（yz

）

x

x

x

xy

x+y

关于字符串的运算292024/9/13

其它如取头字符，取尾部，子串匹配

等

设ω1,ω2,ω3是字母表T上的字符串，称ω1是字符串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，且ω2是字符串ω1ω2ω3的子串。空串是任何字符串的前缀，后缀及子串。

例：

abc的前缀aababcε.后缀cbcabcε.子串abcabbcabcε,

即一个字符串可以看作是多个字符串的连接。

关于字符串的运算302024/9/13

字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1

空串ε的逆还是ε312024/9/13

字母表的幂运算

幂运算设T为字母表，n为任意自然数，定义（1）T0=

（2）设x

Tn-1，a

T，则a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

闭包

T*=

T0T1T2

…

闭包

T+=

T1T2T3

…

T*=T+

，T+=T*

322024/9/13

闭包的物理意义

T的星号闭包T*：字母表T上的所有字符串和空串的集合。

T的正闭包T+：字母表T上的所有字符串构成的集合。 T*=T+∪{ε}举例设T=0，1，则

T0=

，T1=0，1，T2=00，01，10，11，…

T*=

，0，1，00，01，10，11，…

T+=

0，1，00，01，10，11，…

332024/9/13

语言（Languages）

概念设T为字母表，则任何集合L

T*是字母表T上的一个语言（language）

举例

英文单词集

…,English,…,words,…

C

语言程序集

…

字母表？汉语成语集

…,马到成功,…

化学分子式集

…,H2O,…,NaCl,…

any,…

342024/9/13

语言（Languages）举例：设T={a，b}则L1={anbn|n≥1}L3={bk|k

是质数}L2={ε}只有一个空句子的语言L4={}=Φ空语言均为字母表T上的语言。由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。352024/9/13

语言的基本运算语言的积：

两个语言L1和L2的积L1L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T={a,b}，L1和L2是T上的语言。L1={ab,ba}L2={aa,bb}则L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1

语言的积不可交换。362024/9/13

语言的基本运算语言的幂： 语言的幂可归纳定义如下: L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}

第二节文法定义：所谓文法是用来定义语言的一个数学模型表示语言的方法：若语言L是有限集合，可用列举法若L是无限集合（集合中的每个元素有限长度），用其他方法。方法一：文法产生系统，由定义的文法规则产生出语言的每个句子方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。372024/9/13

元语言定义：描述语言的语言 例如：各种各样的程序设计语言当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。382024/9/13

BNF（巴科斯范式） BNF范式通常被作为讨论某种程序设计语言语法的元语言<数字>::=0|1|2|……9::=“定义为”<字母>::=A|B|C|……Z|a|b|……z<标识符>::=<字母>|<标识符><字母>|<标识符><数字>

….通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。BNF定义了一种语言，其中标识符如上定义。BNF描述它所定义的语言，为元语言。392024/9/13

例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。文法是一种元语言，一种方法，根据文法产生出语言的句子。402024/9/13

三、Chomsky文法体系例如：BNF<标识符>::=<字母><标识符>::=<标识符><字母><标识符>::=<标识符><数字><字母>::=a|b|……z|A|B|……|Z<数字>::=0|1|……9将::=改为→表示可被代替用I,L,D分别表示标识符、字母、数字;412024/9/13

则上述表达式可以表示为

I→L

I→IL

I→ID

L→a|b|….|z

D→0|1|….9这就是一个文法的生成式集合。422024/9/13

Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。可见文法的核心是生成式的集合，它决定了语言中句子的产生。432024/9/13

文法的形式定义文法G是一个四元组G=(N，T，P，S)，其中

N

非终结符的有限集合

T

终结符的有限集合N∩T=Φ

P形式为α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*,β∈(N∪T)*

S

起始符且S∈N。442024/9/13

将上例用文法表示 G=(N，T，P，S)N={I,L,D}T={a,b,c,…z,0,1,…9}P={I,La,…,D0,…,D9}S={I}文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。452024/9/13

四．推导与句型1、直接推导 设G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，则有αAγ=>αβγ称αAγ直接推导出αβγ，或说αβγ是αAγ的直接推导。462024/9/13

2、推导序列设G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推导出αi+1（0≤i≤n）,则称序列α0=>α1=>α2=>…=>αn是长度为n的推导序列，而α=α0是长度为0的推导序列。对α推导出α’记为α

α’，若推导序列长度大于0，则记为α

α’。推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。472024/9/13

3、句型和句子句型 字符串α是文法G的句型，当且仅当S

α，且α∈（N∪T）*。

句子ω是G的句子，当且仅当S

ω,且ω∈T*。（ω是由终结符组成的字符串）例：I=>L=>a

I=>IL=>LL=>zL=>zb句型包含句子482024/9/13

4．文法产生的语言由文法G产生的语言记为L(G)。

L(G)={ω|ω∈T*且S

ω}或：

L(G)中的一个字符串，必是由终结符组成的，并且是从起始符S推导出来的。492024/9/13

第三节Chomsky文法体系分类文法G=(N,T,P,S)；P:α→β

其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*属于Chomsky文法体系该体系对生成式的形式做了一些规定，分为四类，即0型、1型、2型、3型文法0型文法：无限制文法 对应的语言：递归可枚举语言，与图灵机等价。502024/9/13

1型文法也称上下文有关文法（CSG：Context-sensitiveGrammar) 生成式的形式为α→β， 其中|α|≤|β|，β∈（N∪T）+，

α∈（N∪T）*N+（N∪T）*对应的语言：上下文有关语言（CSL：Context-sensitiveLanguage)若不考虑ε，与线性有界自动机（LBA,LinearBoundedAutomaton）等价。512024/9/13

2型文法也称上下文无关文法（CFG：Context-freeGrammar)

A→α,

A∈N,且α∈（N∪T）*对应的语言：上下文无关语言（CFL：Context-freeLanguage)。对应的自动机：下推自动机（PDA：PushdownAutomaton)。522024/9/13

3型文法也称正则文法右线性文法（Right-linearGrammar）：A→ωB

或A→ω

A、B∈N,ω∈T*。左线性文法（Left-linearGrammar）： A→Bω或A→ω

A、B∈N,ω∈T*。对应的语言：正则语言对应的自动机：有限自动机（FiniteAutomaton）。532024/9/13

例1： G=({A,B,C},{a,b,d},P,A)

P:A→AB，AB→CAAB，A→d，B→a，C→b

是1型文法。A=>dA=>AB=>dB=>daA=>AB=>ABB=>dBB=>daB=>daaA=>AB=>CAAB=>bAAB=>bdAB=>bdCAAB=>bdbAAB=>bdbdAB=>bdbddB=>bdbdda542024/9/13

例2： G=({A,B,C},{a,b,c},P,A)

P:A→abc

A→aBbc

Bb→bB

Bc→Cbcc

bC→Cb

aC→aaB

aC→aa是1型文法。 其定义的L={anbncn|n≥1}

A=>abc

A=>aBbc=>abBc=>abCbcc=>aCbbcc=>aabbcc

=>aaBbbcc552024/9/13

例3：

G=({S,B,C},{a,b},P,A) P:S→aC,S→bB,B→aS,B→bBB,

B→a,

C→bS,C→aCC,C→b

是2型文法

S=>aC=>ab

S=>aC=>aaCCS=>aC=>abS=>abaC=>ababS=>ababaC=>abababS=>bB=>bbBB=>bbaSB=>bbaaCB=>bbaabB=>bbaaba562024/9/13

例4： G=({A,B,C},{a,b,c},P,A)P:A→Ba；A→c；B→Cb；C→c左线性文法

L={c,cba}正则语言注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法。572024/9/13

四类文法之间的关系只是对生成式形式加以限制0型无限制1型不允许A→ε形式2型3型属于2型不含A→ε的2型、3型属于1型，1型、2型、3型均属于0型。582024/9/13

第三章有限自动机与右线性文法本章主要内容确定有限自动机非确定有限自动机确定与非确定有限自动机的等价性右线性文法和有限自动机的等价性右线性文法的性质(泵浦定理)使用归纳法进行证明的方法592024/9/13

第一节有限自动机一、有限状态系统的概念状态:状态是可以将事物区分开的一种标识。具有离散状态的系统：如数字电路(0,1)，十字路口的红绿灯。离散状态系统的状态数是有限的。具有连续状态的系统：比如水库的水位，室内温度等可以连续变化，即有无穷个状态。有限状态系统必然是离散状态系统（而且状态数有限），因为只有有限个状态。602024/9/13

实例

一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船,每次只能携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢?612024/9/13

622024/9/13

MG－WC（处于左岸的子集－处于右岸的子集）将过河问题模型化：人(M)狼(W)羊(G)菜(C)二、有限自动机的概念有限自动机的概念具有离散输入输出系统的一种数学模型

(可以没有输出，比较特殊的也可以没有输入).有限的状态状态+输入

状态转移每次转换的后继状态都唯一

DFA每次转换的后继状态不唯一

NFA632024/9/13

FA的模型 FA可以理解成一个控制器，它读一条输入带上的字符。642024/9/13

101101有限控制器(1)

控制器包括有限状态；(2)

从左到右依次读取字符；(3)

状态+激励

状态迁移

(根据当前所处状态和输入字符进行状态转移)652024/9/13

有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合有限自动机的五要素q0q1q2q3三、DFA的形式定义定义:DFA是一个五元组M=(Q,T,δ,q0,F)Q:有限的状态集合T:有限的输入字母表δ:转换函数(状态转移集合):Q×T

Qq0:初始状态，q0QF:终止状态集,FQ

662024/9/13

转移图表示的DFA672024/9/13

Q={q0,q1,q2,q3}

T={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}q0q1q2q3682024/9/13

转移表表示的DFA

q0q1q2

q301q2q1q3q0q0q3q1q2

Q={q0,q1,q2,q3}

T={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}四、扩展转移函数适合于输入字符串δ’函数：接收一个字符串的状态转移函数。

:QT*Q

对任何qQ，定义：1.(q,)=q2.若ω是一个字符串,a是一个字符 定义:δ’(q,ωa)=δ(δ’(q,ω),a)

692024/9/13

扩展转移函数适合于输入字符串702024/9/13

q0q1q2

q301q2q1q3q0q0q3q1q2举例

(q0,

)

=q0(q0,0)

=(q0,0)

=q2(q0,00)

=(q2,0)

=q0(q0,001)

=(q0,1)

=q1(q0,0010)

=(q1,0)

=q3q0q1q2q3DFA接受的语言被DFA接收的字符串:输入结束后使DFA的状态到达终止状态。否则该字符串不能被DFA接收.DFA接收的语言:被DFA接收的字符串的集合. L(M)=

w

(q0,w)F

例：T={0，1}712024/9/13

接收含有奇数个0的任意串五、格局为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当前状态q，待输入字符串w。两者构成一个瞬时描述，用（q,w）表示，称为格局。初始格局：（q0,w)终止格局：(q,ε),q

F722024/9/13

如图，接受001010的格局（q0,001010）┝(q2,01010)┝(q0,1010)┝(q1,010)┝(q3,10)┝(q2,0)┝(q0,ε)格局数量是无限的。有限状态自动机是无记忆的。例如接受0010101111和接受01011111时，都可以进入格局(q0,1111)。732024/9/13

格局示例q0q1q2q3如果对某个q

F,有(q0,w)

┝(q,

),则称输入字符串w是可被确定的有限自动机接受的。742024/9/13

设计有限自动机自动机的设计是一个创造过程，没有简单的算法或过程。技巧：假设自己是机器，思考如何去实现机器的任务。为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。

例：构造自动机，识别所有由奇数个a和奇数个b组成的字符串。关键：不需要记住所看到的整个字符串，只需记住至此所看到的a、b个数是偶数还是奇数。

752024/9/13

q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第二节 不确定的有限自动机(NFA) 修改DFA的模型，使之在某个状态，对应一个输入，可以有多个转移，到达不同的状态，则称为不确定的有限自动机。

例：762024/9/13

(1)(2)一、不确定有限自动机的形式定义NFA是一个五元组，M=(Q,T,δ,q0,F)。

其中δ是Q×T->2Q的函数，其余与DFA相同。如果接收一个字符串后NFA进入一个状态集，而此集合中包含一个以上F中的状态，

则称NFA接收该字符串。772024/9/13

782024/9/13

(1)(2)pq

r0{q}

{q}

{q,r}

1pq

r0{p}{r}

{r}

1{p,q}转移图和转移表表示的NFA格局示例如图所示，用格局序列描述自动机的工作过程，当输入字符串是011011时，则有792024/9/13

二、NFA的状态转移函数与DFA唯一不同之处:Q

2Q同样，

δ可扩展为δ’

(

:QT*2Q)1.δ’(q,ε)

=

{q}

含义：

不允许无输入的状态变化。2.δ'(q,ωa)={p|存在r∈δ'(q,ω)∧p∈δ(r,a)}含义:δ’(q,ωa)对应的状态集合是δ’(q,ω)对应的每个状态下再接收字符a以后可能到达的状态集合的并集.

即若(q

,ω)={r

1,r

2,,r

k},则

(q

,ωa)=(r

i,a)其中ω

T*,a

T，r

i

Q802024/9/13

812024/9/13

举例

(p

,

)

={p}

(p

,0)

={q}

(p

,01)

={q,r}

(p

,010)

={q}

(p

,0100)

={q}

(p

,01001)={q,r}

pq

r0{q}

{q}

{q,r}

1扩展转移函数适合于输入字符串822024/9/13

NFA

接受的语言

设一个NFAA=(Q,

T,

,q0,F)

定义A的语言:

L(A)=

w

(q0,w)

F

第三节

NFA与DFA的等价性DFA是NFA的特例，所以NFA必然能接收DFA能接收的语言。

因此证明等价性只要能够证明一个NFA所能接收的语言必能被另一个DFA所接收。1.定理：设一个NFA接受语言L，那么必然存在一个DFA接受L。2.

证明:策略：对于任意一个NFA，构造一个接收它所能接收语言的DFA，这个DFA的状态对应了NFA的状态集合。832024/9/13

842024/9/13

从NFA构造等价的DFA(子集构造法)设L是某个NFAMN=(QN,

T,

N,q0,FN)的语言,则存在一个DFAMD,满足L(MD)=L(MN)=L.

证明:定义

MD=(QD,

T,

D,{q0},FD

),

其中

QD

=

S

S

QN

=2Q

对S

QD

和aT

,

D(S,a)=

N(q,a)，

FD=

S

S

QN

S

FN

需要证明:对任何w

T*

,

D({q0}

,w)=

N(q0,w).

归纳于|w|可证上述命题.

q

S852024/9/13

pq

r0{q}

{q}

{q,r}

10

{q}1

{p}{q}

{r}{p,q}

{p,r

}

{q,r

}

{p,q,r

}

{q}{q,r}

{q}{q,r}{q}

{q}{q,r}{q}{q,r}

子集构造法举例862024/9/13

pq

r0{p}{r}

{r}

1{p,q}01{p}

{p,q,r}{p}{p,q}{p}{p,q}{p,q}{p,r}{p,q,r}

{p,r}{p,r}{p,q,r}子集构造法举例872024/9/13

证明:从NFA构造等价的DFA设MN=(QN,

T,

N,q0,FN)是一个NFA

,通过子集构造法

得到相应的DFAMD=(QD,

T,

D,{q0},FD

),则对任何w

T*

,

D({q0}

,w)=

N(q0,w).

证明:归纳于|w|1设|w|=0,即

w=

.由定义知

D({q0}

,

)=

N(q0,

)={q0}

.2

设|w|=n+1,并

w=xa,a

T.注意到|x|=n.假设

D({q0}

,x)=

N(q0,x)={p1,p2,

,pk

}.则

D({q0}

,w)=

D(

D({q0}

,x),a)=

D({p1,p2,

,pk

},a)=

N(pi,a).=

N(q0,w)i=1k882024/9/13

实践中,通过子集构造法得到的DFA的状态数目与原NFA的状态数目大体相当.

在较坏的情况下,上述DFA的状态数目接近于所有子集的数目.

举例由如下NFA构造的DFA的状态数目至少为2n子集构造法得到的状态数q0q1q2qn第四节 有

转换的NFA一、定义 概念：当输入空串ε(无输入)时，也能引起状态的转移。例：892024/9/13

输入“002”时的转移格局：

q0q1q2012εε902024/9/13

-NFA的形式定义一个

-NFA

是一个五元组A=(Q,

T,

,q0,F).有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合q0

Q

F

Q与NFA的不同之处:Q(T

)

2Q912024/9/13

-NFA如何接受输入符号串q1q0q2q3q5

,+,–q4

该

-NFA可以接受的字符串如：

3.14

+.314

–314.922024/9/13

二、

-闭包（closure）概念

状态q的

-闭包，记为

-

CLOSURE或ECLOSE

，定义为从q经所有的

路径可以到达的状态（包括q自身），如：

q0q1q2012εε

-CLOSURE

(q0)={q0,q1,q2}

-CLOSURE

(q1)={q1,q2}

-CLOSURE

(q2)=

{q2

}状态子集I的ε-闭包： ε-CLOSURE(I)＝

∪

ε-CLOSURE(q)q∈I例： ε-CLOSURE({q1，q2})＝ε-CLOSURE(q1)∪ε-CLOSURE(q2)＝{q1，q2}Ia概念：对于状态子集I

Q，任意a∈T，定义Ia如下：

Ia=ε-Closure(P) 其中P=δ（I，a）.即P是从I中的状态经过一条标a的边可以到达的状态集合932024/9/13

942024/9/13

例：I＝{q0，q1}，求I1I1＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε952024/9/13

扩展转移函数适合于输入字符串设一个

-NFA,

:Q

T

2Q

扩充定义:QT*2Q

对任何qQ，定义：1(q,)=ECLOSE(q)2δ'(q，ωa)＝ε-CLOSURE(P)其中P＝{p|存在r∈δ'(q，ω)∧p∈δ(r，a)}注意：此时δ(q，a)δ'(q，a)，因为δ(q，a)表示由q出发，只沿着标a的路径所能到达的状态，而δ'(q，a)表示由q出发，沿着标a(包括ε转换在内)的路径所能到达的状态.962024/9/13

ε-NFA中，δ与δ’函数的不同

举例计算(q0,a)

δ'(q0，ε)＝ε-CLOSURE(q0)＝{q0，q2}δ'(q0，a)＝ε-CLOSURE(δ(δ'(q0，ε)，a))＝ε-CLOSURE(δ({q0，q2}，a))＝ε-CLOSURE(δ(q0，a)∪δ(q2，a))＝ε-CLOSURE({q1}∪{q3})＝{q1，q2}∪{q3}＝{q1，q2，q3}同理：δ'(q0，aa)＝{q3}ε-CLOSURE(q0)＝{q0，q2}ε-CLOSURE(q1)＝{q1，q2}ε-CLOSURE(q2)＝{q2}ε-CLOSURE(q3)＝{q3}972024/9/13

三、-NFA

的

语言

设一个

-NFAM=(Q,

T,

,q0,F)

定义M

的语言：

L(M)=

ω|(q0

,ω)

F

即

满足δ'(q0，ω)含有F的一个状态

四、有

转换的NFA与无

转换的NFA的等价1.

-NFA<==>NFA

具有

转移的NFA是不具

转移的NFA的一般情况，所以只要证明下面的定理即可：定理：如果L被一个具有

转移的NFA接收，

那么L可被一个不具

转移的NFA接收。证明思路：构造一个不具

转移的NFA，证明其接收具有

转移的NFA所接受的语言。982024/9/13

992024/9/13

从

-NFA构造等价的无

NFA设M=(Q,T,

,q0,F)是一个

-NFA，可构造一个无

的NFAM1=(Q,T,

1

,q0,F1)，

对任何aT,

1(q,a)=

(q

,a)。

（注意δ与δ’的区别与联系。而δ1和δ’是相等的。）F1

＝F∪{q0}若ε-CLOSURE(q0)

F

F否则{1002024/9/13

从

-NFA构造等价的无

NFA证明:采用归纳法证明δ1（q0，ω）＝δ’（q0，

ω），|ω|>=1。当|w|=0,即w=

时，不一定相等.∵δ1(q0，ε)＝{q0}，

而δ’(q0，ε)＝ε-CLOSURE(q0) 因此，从|ω|＝1开始证明当|ω|=1时，定义相等。 由δ1定义δ1（q0，a）＝δ’（q0，a）设当|ω|<=n时，δ1（q0,ω）=δ’（q0,ω），则当|ωa|=n+1时，左侧＝δ1（q0,ωa）

＝δ1(δ1（q0，ω），a) ＝δ1(δ’（q0，ω），a)由归纳假设 ＝δ1(R，a)设R＝δ’（q0，ω） ＝∪δ1(q，a)q∈R ＝∪δ’(q，a)q∈R.由δ1定义 ＝δ’(R，a)＝δ’(δ’（q0，ω），a)∵R＝δ’（q0，ω） ＝δ’(q0，ωa) ＝右侧再证:δ1（q0，ω）含F1的一个状态当且仅当δ’（q0，ω）含F的一个状态（略）1012024/9/13

证明同时展示了一种将

-NFA转化为NFA的方法.

-NFA

<==>

NFA

<==>

DFA例：将

-NFA转换为NFA.（图3.4.1，3.4.3）1022024/9/13

q0q1q2012εεq0q1q20120,11,20,1,21032024/9/13

举例q1q0q2q3q5

,+,–q4{q0}{q1}{q1q4}{q2}{q2q3q5}{q3q5}1042024/9/13

第五节

正则集和正则式正则集：字母表上一些特殊形式的字符串的集合，是正则式所表示的集合。

正则式：用类似代数表达式的方法表示正则语言。运算:作用于语言上的三种代数运算

联合（union）

连接（concatenation）（星）闭包（closure）

1052024/9/13

正则表达式（regularexpression）归纳定义正则表达式如下：基础：ε，

，a（a∈T）都是正则式(原子正则式)， 相应的正则集为{ε}，

，{a}归纳：如果A和B是正则式，且分别代表集合L(A)和L(B)，则(A+B)，(A.B)，A*也是正则式，分别表示以下正则集：L(A)∪L(B)(语言A/语言B的串)L(A).L(B) (两个语言中的串的连接)L(A)* (语言A中的串的多次连接)仅通过有限次使用以上两步定义的表达式，才是字母表T上的正则式。这些正则式所表示的字符串集合是T上的正则集。

1062024/9/13

正则表达式算符优先级算符优先级（precedence）依次为

（closure）

•连接（concatenation）

（union）定义：若两个正则式表示相同的正则集，则称这两个正则式相等。即R1＝R2<==>L(R1)=L(R2)注1：正则集是T*的子集。注2：L+包含ε当且仅当L包含ε。注3：每个正则集至少对应一个正则式（可有无穷多个正则式）1072024/9/13

正则表达式举例书p55例1表示如下语言的正则表达式：语言中的每个字符串由交替的0

s和1

s

构成

(01)*+(10)*+0(10)*+1(01)*

(+1)(01)*(+0)

(+0)(10)*(+1)1082024/9/13

语言的联合（union）运算两个语言L和M的联合

L

M=

w

w

L

w

M

举例设L=

001,10,111

,

M=

,001

,则

L

M=

,10,001,111

1092024/9/13

语言的连接（concatenation）运算

两个语言L和M的连接

L·

M=

w1w2

w1

L

w2

M

有时记L·

M为LM

举例设L=

001,10,111

,

M=

,001

,则

LM=

001,10,111,001001,10001,111001

1102024/9/13

语言的闭包（closure）运算语言L的闭包

L*=

wn

w

L

n0

,其中wn为w

的n次连接或L*=L0

L1

L2

…=

i0

Li,其中

L0=

，L1=L,L2=LL,…

举例设L=

0,11

,

则

L*=

,

0,11,00,011,110,1111,000,0011,0110,01111,1100,11011,11110,111111,…

1112024/9/13

正则式的性质交换律（commutativity）和结合律（associativeity）(1)(α+β)+γ＝α+(β+γ)(2)(αβ)γ＝α(βγ)(3)α+β＝β+α等幂律（idempotentlaw）(4)α+α＝α分配律（distributivelaw）(5)α(β+γ)＝αβ+αγ(6)(β+γ)α＝βα+γα1122024/9/13

正则式的性质幺元（identities）和零元（annihilators）(7)α+φ＝φ+α＝α(8)αφ＝φα＝φ(9)αε＝εα＝α

与闭包相关的定律(10)(α*)*＝α*(11)α*＝α+α*

*=

*=

L+=LL*=L*L（L+的定义）L*=L++

1132024/9/13

正则式的性质(11)α*＝α+α*

证明：∵α*＝ε＋α＋α2＋…＋αn

L(α*)＝{ε}∪L(α)∪L(α2)∪…∪L(αn)L(α+α*)＝L(α)∪({ε}∪L(α)∪L(α2) ∪…∪L(αn))＝L(α)∪L(α*)而L(α)L(α*)∴α+α*＝α*1142024/9/13

右线性文法与正则式

右(左)线性文法又称为正则文法，右线性文法与正则式可以用来代表同一正则语言。二者具有等效性。

例：文法S

aS，S

a 对应正则式：a+，或者a*a1152024/9/13

从右线性文法导出正则式求解规则:设x

=αx+β，α∈T*，β∈(N∪T)*,x∈N则x的解为x＝α*β证明：x

=αx+β表示x有两个生成式：x

αx

和x

β，生成的语言为（β，αβ，ααβ，αααβ,…），显然该语言可用正则式α*β表示。

1162024/9/13

举例（P56例2）设右线性文法G=({S,A,B},{a,b},P,S}，生成式P如下：S→aA,S→bB,S→b,A→bA,A→,B→bS以上生成式写成联立方程为 S=aA+bB+b（1） A=bA+（2） B=bS（3）对式（2）利用规则R和性质α=α得

A=b*4）将式（4）和式（3）代入式（1）中的A、B，得 S=ab*+bbS+b=bbS+ab*+b=(bb)*(ab*+b)所以由G产生的语言用正则式表示为(bb)*(ab*+b)

1172024/9/13

第六节正则集和右线性文法正则集是由右线性文法产生的语言由右线性文法产生的语言都是正则集(一).求证正则集是由右线性文法产生的语言证明方法：

找出相应的右线性文法，使之产生的语言是这些正则集。1182024/9/13

首先从最简单的正则式出发，求证其正则集Φ，{ε}，{a}是右线性语言。证明：对正则集Φ，有右线性文法G＝{{S}，T，Φ，S}，使L(G)=Φ对正则集{ε},有右线性文法G＝{{S}，T，{S->ε}，S}，使L(G)={ε}对正则集{a}，有右线性文法G＝{{S}，T，{S->a}，S}，使L(G)={a}

1192024/9/13

将对由并，积，闭包形成的正则集的证明，改为对右线性语言的证明。 设在字母表T上，有语言L1和L2，则L1∪L2，L1.L2，L1*都是右线性语言。证明方法：分别找出相应的右线性文法。设G1＝（N1，T，P1，S1）产生L1G2＝（N2，T，P2，S2）产生L2N1N2＝Φ(若不为空,则可对N中符号换名)1202024/9/13

构造G＝（N，T，P，S）产生L，使L=L1∪L2其中 N＝N1∪N2∪{S},S为新的非终结符；

P＝P1∪P2∪{S－>S1，S－>S2}先证LL1∪L2：在G中，由G的定义，对于任意ω，意味着或者（按G1的产生式），或者（按G2的产生式）即文法G的每个句子或由G1产生，或由G2产生。∴L(G)L(G1)∪L(G2)再证L1∪L2L：设有ω∈L1∪L2，则存在推导S1

G1＝>+ω或S2

G2＝>+ω∴必有SG＝>+ω。即L1∪L2L。命题得证＃

(a).求证L1∪L2是右线性语言1212024/9/13

构造G＝（N，T，P，S）其中N＝N1UN2，S＝S1，生成式P为:若A->αB∈P1，则它也属于P 若A->α∈P1，则A->αS2∈P P2P先证L(G1).L(G2)L(G)

若有任意S1＝>*ω1

与S2＝>*ω2分别属于G1和G2定义的语言中，那么有S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1

和

S2＝>β1A1＝>β2B2＝>β3C3＝>…＝>ω2

，∴S＝>S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1.S2＝>*ω1.ω2

∴L(G1).L(G2)L(G)(b).求证L1L2是右线性语言1222024/9/13

再证L(G)

L(G1).L(G2)若有S＝>S1＝>α1A＝>α2B＝>α3C＝>… ＝>ω1.S2＝>*ω1.ω2

那么则必然在G1和G2中同时有

S1＝>α1A＝>α2B＝>α3C＝>…＝>ω1

和

S2＝>β1A1＝>β2B2＝>β3C3＝>…＝>ω2∴L(G)L(G1).L(G2)命题得证＃

(b).求证L1.L2是右线性语言1232024/9/13

证明:构造G＝（N，T，P，S）其中；N＝N1US，

SN1，S是一个新的非终结符，生成式P为: 如果A->

αB∈P1，则A->

αB∈P。 如果A->

α∈P1，则A->

αS∈P S->S1，S->ε∈P。先证L(G)

L(G1)*若有S＝>S1＝>ω1S＝>*ω1ω2S＝>… ＝>*ω1ω2…ωi.S＝>ω1ω2…ωi则在G1中必然有

S1＝>*ω1

；S1＝>*ω2；。。。；S1＝>*ωi∴L(G)L(G1)*(c).求证L1*是右线性语言1242024/9/13

再证L(G1)*

L(G)若G1中有

S1＝>*ω1

；S1＝>*ω2；。。。；S1＝>*ωi则在G中必然有S＝>S1＝>ω1S＝>*ω1ω2S＝>… ＝>*ω1ω2…ωi.S＝>ω1ω2…ωi∴L(G1)*L(G) 因此L*可以用右线性文法描述。证毕＃(c).求证L1*是右线性语言(续)1252024/9/13

思路：

由给定的右线性文法可找出正则式，而正则式表示的语言即为正则集。方法：对右线性文法构造标准形式的正规表达式方程组，应用规则x＝αx+β＝>x＝α*β进行消元，求解方程组，即可得出正规表达式。由(一)和(二)即可得出下定理:定理:

一个语言是正则集，当且仅当该语言为右线性语言。(二).证明由右线性文法产生的语言是正则集1262024/9/13

3.7正则表达式与有限自动机的关系结论:有限自动机、右（左）线性文法、正则表达式都定义