形式语言与自动机理论二课件

形式语言与自动机理论山东大学计算机科学与技术学院2007.3形式语言与自动机理论山东大学计算机科学与技术学院2007.31第四章正规表达式4.1正规表达式的形式定义定义：设是一个字母表，字母表上正规式（RegularExpression,RE）和正规集定义如下：（1）是上的正规式，对应的正规集为；（2）是上的正规式，对应的正规集为{}；（3）对a，a是上的正规式，对应的正规集为{a}；第四章正规表达式4.1正规表达式的形式定义定义：设是2第四章正规表达式4.1正规表达式的形式定义（4）如果r和s分别是上的正规式，对应的正规集为R和S。那么(r+s)为正规式，对应的正规集为RS；(rs)为正规式，对应的正规集为RS；(r*)为正规式，对应的正规集为R*（5）只有满足上述形式定义的表达式才是上的正规式，它所表达的语言是正规集。第四章正规表达式4.1正规表达式的形式定义（4）如果r和3第四章正规表达式正规表达式的运算性质假设r,s,t都是上正规式，则有以下性质：（1）结合律；（2）分配律；（3）交换律；（4）幂等律；（5）加运算单位元；（6）乘运算单位元；（7）乘运算零元；（8）(r*)*=r*；（9）r*=r++；（10）*=（11）*=

4.1正规表达式的形式定义第四章正规表达式正规表达式的运算性质4.1正规表达式的形4第四章正规表达式4.2正规表达式与FA的等价假设r是上的正规式，M是一个FA。若L(r)=L(M)，则称正规式r

与FAM等价。第四章正规表达式4.2正规表达式与FA的等价假设5第四章正规表达式4.2正规表达式与FA的等价定理：每个正规表达式r都存在一个

-NFAM

使得L(M)

=

L(r)。(1)运算符个数为0q0qfq0aq0qf第四章正规表达式4.2正规表达式与FA的等价定理：每个正6第四章正规表达式定理：每个正规表达式r都存在一个

-NFAM

使得L(M)

=

L(r)。(2)运算符个数不为0

r=r1+r2

M2M1q0f1q1f2q2f0

第四章正规表达式定理：每个正规表达式r都存在一个-N7第四章正规表达式定理：每个正规表达式r都存在一个

-NFAM

使得L(M)

=

L(r)。(2)运算符个数不为0

r=r1r2M2M1f1q1f2q2

第四章正规表达式定理：每个正规表达式r都存在一个-N8第四章正规表达式定理：每个正规表达式r都存在一个

-NFAM

使得L(M)

=

L(r)。(2)运算符个数不为0

r=r1*

M1q0f1q1f0

第四章正规表达式定理：每个正规表达式r都存在一个-N9第四章正规表达式4.2正规表达式与FA的等价定理：设L是被DFAM接受的语言，则L可以被正规表达式表示。-NFANFADFARGRE第四章正规表达式4.2正规表达式与FA的等价定理：设L10第五章正规语言的性质5.1Pumping引理定理：假设

为有限字母表，L

*。若L是正规语言，那么存在正整数n使得对任意的w1,w2,w3

*,当w1w2w3L并且|w2|n,可以写成w2=,这里，，||n.则w1

kw3L(k=0,1,2,….)。(1)Pumping引理的提出第五章正规语言的性质5.1Pumping引理定理：假设11第五章正规语言的性质5.1Pumping引理(1)Pumping引理的提出Pumping引理：假设L是正规集，那么存在正整数n使得当w

L并且|w|n,就可以写出w=，这里，，||n，且对k0,则

kL。第五章正规语言的性质5.1Pumping引理(1)P12第五章正规语言的性质5.1Pumping引理(2)Pumping引理的应用例1：证明L1={anbn|n1}不是RL。例2：证明L2={w|w

*且={0,1},w=w-1}

不是RL。这里w是回文。即w与w的逆相同。第五章正规语言的性质5.1Pumping引理(2)P13第五章正规语言的性质5.1Pumping引理(2)Pumping引理的应用例3：证明L3={an2|nN}不是RL。例4：证明L4={ap|p是素数}不是RL。第五章正规语言的性质5.1Pumping引理(2)P14第五章正规语言的性质5.2正规语言的封闭性正规语言在并、乘积、闭包运算下是封闭的；(2)正规语言类在补运算下是封闭的；(3)正规语言类在交运算下是封闭的；第五章正规语言的性质5.2正规语言的封闭性正规语言在并15第五章正规语言的性质5.2正规语言的封闭性(4)

代换定义：设，是两个字母表，映射

f:

p(

*)称为到的代换。如果对a,f(a)是上的RL，则称f是正则代换或正规代换。正规语言类在代换下是封闭的。第五章正规语言的性质5.2正规语言的封闭性(4)代换定16第五章正规语言的性质(5)同态5.2正规语言的封闭性定义：设，是两个字母表，映射

f:

*如果对x,y

*,有f(xy)=f(x)f(y)，则称f是从

到*的同态映射。正规语言在同态和逆同态下是封闭的。第五章正规语言的性质(5)同态5.2正规语言的封闭性定17第五章正规语言的性质5.2正规语言的封闭性正规语言在商运算下是封闭的。定义：假设L1,L2

*,则L1和L2的商定义为：

L1/L2={x|yL2，使得xyL1}第五章正规语言的性质5.2正规语言的封闭性正规语言在商运18第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化一、相关概念1、等价关系2、划分3、划分加细4、等价类5、商集6、等价关系的指数第五章正规语言的性质5.3Myhill-Nerode定理19第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化二、Myhill-Nerode定理定理：假设是有限字母表，L

*,以下三个命题等价：（1）L是正规语言；（2）L是*上具有有穷指数的右不变等价关系的某些等价类的并；（3）如果RL={<x,y>|x,y

*,对z

*,xzL当且仅当yzL}，则RL的指数有穷。第五章正规语言的性质5.3Myhill-Nerode定理20第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化例：假设L=0*10*它被下列自动机接受。能否简化？q0q1q2q3q4q500110110100,1q0:(00)nR(00)mq1:0(00)nR(00)m0q2:(00)n1R(00)m1q3:(00)n01R(00)m01q4:(0)n10(0)mR(0)p10(0)qq5:xRmy,x和y至少含有两个1的串。(这里m,n,p,q0)第五章正规语言的性质5.3Myhill-Nerode定理21第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化二、Myhill-Nerode定理推论1：对任意正规语言L，如果DFAM满足L(M)=L，则|*/RL||Q|推论2：在同构（即状态重新命名）的意义下，接受一个语言L的最小DFA是唯一的。第五章正规语言的性质5.3Myhill-Nerode定理22第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化三、DFA的极小化1、状态等价和可区分设DFAM=(Q,,,q0,F)，如果

x*，使得Q中的两个状态q1,q2，(q1,x)F和(q2,x)F中仅有一个成立，则称q1和q2是可区分的。若对不同的状态q1,q2和任意的串x

*，有(q1,x)F当且仅当(q2,x)F。则称q1和q2是等价的，记为q1

q2。第五章正规语言的性质5.3Myhill-Nerode定理23第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化三、DFA的极小化2、利用等价和可区分概念，标记填表求极小化（1）构造一个二维表（2）标识可区分状态（3）对剩余的每对状态进行标识（4）重复（3）直到所有状态对处理完毕。第五章正规语言的性质5.3Myhill-Nerode定理24第五章正规语言的性质例：设DFAM=({q0,q1,..,q5},{0,1},,q0,F)q2q0q1q4q3q5010100111100第五章正规语言的性质例：设DFAM=({q0,q1,..25第五章正规语言的性质5.3Myhill-Nerode定理和DFA极小化四、正规语言的判定算法1、空性、有穷性、无穷性定理：具有n个状态的有限自动机接受的串集合是：（1）非空的当且仅当这个有限自动机接受一个长度小于n的串，