Chapter 02--形式语言与自动机

1、LI Wensheng, SCS, BUPT 第第2 2章章 形式语言形式语言与自动机基础与自动机基础知识点：文法的形式定义知识点：文法的形式定义 上下文无关文法、正规文法上下文无关文法、正规文法 推导、短语、分析树、二义性推导、短语、分析树、二义性 有限自动机的形式定义有限自动机的形式定义 自动机、文法、表达式等价性自动机、文法、表达式等价性 NFANFA的确定化、的确定化、DFADFA的最小化的最小化Wensheng Li BUPT形式语言与自动机基础形式语言与自动机基础2.1 2.1 语言和文法语言和文法2.2 2.2 有限自动机有限自动机2.3 2.3 正规文法与有限自动机的等价性正规

2、文法与有限自动机的等价性2.4 2.4 正规表达式与有限自动机的等价性正规表达式与有限自动机的等价性2.5 2.5 正规表达式与正规文法的正规表达式与正规文法的等价性等价性 小结小结 2Wensheng Li BUPT2.1 2.1 语言和文法语言和文法 一、字母表和符号串一、字母表和符号串 二、语言二、语言 三、文法及其形式定义三、文法及其形式定义 四、推导和短语四、推导和短语 五、分析树及二义性五、分析树及二义性 六、文法的变换六、文法的变换3Wensheng Li BUPT一、字母表和符号串一、字母表和符号串字母表字母表u符号的非空有限集合符号的非空有限集合u典型的符号是字母、数字、各种

3、标点和运算符等。典型的符号是字母、数字、各种标点和运算符等。符号串符号串u定义在某一字母表上定义在某一字母表上u由该字母表中的符号组成的有限符号序列由该字母表中的符号组成的有限符号序列u同义词：句子、同义词：句子、字字4Wensheng Li BUPT符号串有关的几个概念符号串有关的几个概念n长度长度u符号串符号串 的长度是指的长度是指 中出现的符号的个数，记作中出现的符号的个数，记作| | | |。u空串的长度为空串的长度为0 0，常用，常用 表示表示。n前缀前缀u符号串符号串 的前缀是指从符号串的前缀是指从符号串 的末尾删除的末尾删除0 0个或多个符号个或多个符号后得到的符号串。如：后得到

4、的符号串。如：univuniv 是是 university university 的前缀的前缀n后缀后缀u符号串符号串 的后缀是指从符号串的后缀是指从符号串 的开头删除的开头删除0 0个或多个符号个或多个符号后得到的符号串。如：后得到的符号串。如：sitysity 是是 university university 的后缀的后缀n子串子串u符号串符号串 的子串是指删除了的子串是指删除了 的前缀和的前缀和/ /或后缀后得到的符或后缀后得到的符号串。如：号串。如：verver 是是 university university 的子的子串串5Wensheng Li BUPT符号串有关的几个符号串有关的

5、几个概念（续）概念（续）n真真前缀前缀、真后缀真后缀、真子串真子串u如果非空符号串如果非空符号串 是是 的前缀、后缀或子串，并且的前缀、后缀或子串，并且，则，则称称 是是 的真前缀、真后缀、或真子串。的真前缀、真后缀、或真子串。n子序列子序列u符号串符号串 的子序列是指从的子序列是指从 中删除中删除0 0个或多个符号个或多个符号( (这些符号这些符号可以是不连续的可以是不连续的) )后得到的符号串。如：后得到的符号串。如：nvstnvst6Wensheng Li BUPTn连接连接u符号串符号串 和符号串和符号串 的连接的连接是把符号串是把符号串 加在符号串加在符号串 之之后得到的符号串后得到

6、的符号串u若若 =ab=ab， =cd=cd，则，则= =abcdabcd，= =cdbacdba。u对任何符号串对任何符号串 来说，都有来说，都有= = = n幂幂u若若 是符号串，是符号串， 的的n n次幂次幂 n n 定义为：定义为： n n个个当当n=0n=0时，时， 0 0是空串是空串 。假如假如 =ab=ab，则有：，则有： 0 0= = 1 1=ab =ab 2 2= =abababab n n= =abababababab n n个个abab7符号串运算符号串运算Wensheng Li BUPT二、语言二、语言语言：语言：在某一确定字母表上的符号串的集合在某一确定字母表上的符号

7、串的集合。u空集空集 ，集合，集合 也是符合此定义的语言。也是符合此定义的语言。u这个定义并这个定义并没有把任何意义赋予语言中的符号串没有把任何意义赋予语言中的符号串。语言的运算：语言的运算：假设假设 L L 和和 M M 表示表示两个语言两个语言nL L和和M M的的并并记作记作LMLM：LM=LM=s|ss|s L L 或或 s s M M nL L和和M M的的连接连接记作记作LMLM：LM=LM=st|sst|s L L 并且并且 t t M M nL L的的闭包闭包记作记作L L* *：即：即L L的的0 0次或若干次连接。次或若干次连接。i=0L*=Li = L= L0 0LL1

8、1LL2 2LL3 3 nL L的的正闭包正闭包记作记作L L+ +：即：即L L的的1 1次或若干次连接。次或若干次连接。i=1L+=Li = L = L1 1LL2 2LL3 3LL4 4 8Wensheng Li BUPTnL=A,B, L=A,B, ,Z,a,b, ,Z,a,b, ,z ,z，D=0,1, D=0,1, ,9 ,9u可以把可以把L L和和D D看作是字母表看作是字母表u可以把可以把L L和和D D看作是语言看作是语言n语言运算举例：语言运算举例：n把把幂运算推广幂运算推广到语言到语言L L0 0= ，L Ln n=L=Ln-1n-1L L，于是，于是L Ln n是语言是

9、语言L L与其自身的与其自身的n-1n-1次连接。次连接。 语言语言 描述描述 LD LD 全部字母和数字的集合全部字母和数字的集合 LD LD 由一个字母后跟一个数字组成的所有符号串的集合由一个字母后跟一个数字组成的所有符号串的集合 L L4 4 由由4 4个字母组成的所有符号串的集合个字母组成的所有符号串的集合 L L* * 由字母组成的所有符号串（包括由字母组成的所有符号串（包括 ）的集合）的集合 L(LD) L(LD)* * 以字母开头，后跟字母、数字组成的所有符号串的集合以字母开头，后跟字母、数字组成的所有符号串的集合 D D+ + 由一个或若干个数字组成的所有符号串的集合由一个或若

10、干个数字组成的所有符号串的集合9Wensheng Li BUPT三、文法及其形式定义三、文法及其形式定义n文法文法：所谓文法就是描述语言的语法结构的形式规则。：所谓文法就是描述语言的语法结构的形式规则。n任何一个文法都可以表示为一个任何一个文法都可以表示为一个四元组四元组G=(VG=(VT T,V,VN N,S, ,S, ) ) V VT T是一个非空的有限集合，它的每个元素称为是一个非空的有限集合，它的每个元素称为终结符号终结符号。 V VN N是一个非空的有限集合，它的每个元素称为是一个非空的有限集合，它的每个元素称为非终结符号非终结符号。 V VT TVVN N = = S S是一个特殊

11、的非终结符号，称为文法的是一个特殊的非终结符号，称为文法的开始符号开始符号。 是一个非空的有限集合，它的每个元素称为是一个非空的有限集合，它的每个元素称为产生式产生式。n产生产生式的形式为：式的形式为：“” 表示表示 “定义为定义为”（或（或“由由组成组成”） 、(V(VT TVVN N) )* * ，n左左部相同的产生式部相同的产生式1 1、2 2、n n可以缩写可以缩写 1 1| | 2 2| | | n n“| |” 表示表示 “或或”， 每个每个 i i( (i i=1,2,=1,2,n),n)称为称为 的一个的一个候选式候选式10Wensheng Li BUPT文法类型文法类型 产生

12、式形式的限制产生式形式的限制 文法产生的语言类文法产生的语言类 0 0型文法型文法 其中其中 , ,(V(VT TVVN N) )* * 0 0型语言型语言 | | | | 0 0 1 1型文法，即型文法，即 1 1型语言，即型语言，即上下文有关文法上下文有关文法 其中其中 , ,(V(VT TVVN N) )* * 上下文有关语言上下文有关语言 | | | | | | | | 2 2型文法，即型文法，即 A A 2 2型语言，即型语言，即上下文无关文法上下文无关文法 其中其中 A A V VN N，(V(VT TVVN N) )* * 上下文无关语言上下文无关语言 3 3型文法，即型文法，即

13、 A Aa a或或A AaBaB（右线性），或（右线性），或 3 3型语言，即型语言，即 正规文法正规文法 A Aa a或或A ABaBa（左线性）（左线性） 正规语言正规语言 （线性文法）（线性文法） 其中其中 A,BA,B V VN N， a a V VT T 11文法分类文法分类n根据对产生式施加的限制不同，定义了四类文法根据对产生式施加的限制不同，定义了四类文法和和 相应的四种形式语言类。相应的四种形式语言类。Wensheng Li BUPT上下文无关文法及相应的语言上下文无关文法及相应的语言n所定义的语法单位所定义的语法单位( (或称语法实体或称语法实体) )完全独立于这种完全独立于

14、这种语法单位可能出现的上下文环境语法单位可能出现的上下文环境n现有程序设计语言中，许多语法单位的结构可以用现有程序设计语言中，许多语法单位的结构可以用上下文无关文法来描述。上下文无关文法来描述。例：描述算术表达式的文法描述算术表达式的文法G G： G=(G=(i i,+,-,+,-,* *,/,(,),/,(,), ) )其中其中 ： + | | - | | * * | | / | | () | ) | i in语言语言L(G)L(G)是所有包括加、减、乘、除四则运算的算是所有包括加、减、乘、除四则运算的算术表达式的集合。术表达式的集合。12Wensheng Li BUPTn元语言：元语言：:

15、= := 表示表示 “定义为定义为” 或或 “由由组成组成” 表示非终结符号表示非终结符号| | 表示表示“或或”n算术表达式文法的算术表达式文法的BNFBNF表示：表示： := := + | | - | | := := * * | | / | | := ( := () | ) | i iBNFBNF（Backus-Normal FormBackus-Normal Form）表示法）表示法13Wensheng Li BUPT文法书写约定文法书写约定n终结符号终结符号u次序靠前的小写字母，如：次序靠前的小写字母，如：a a、b b、c cu运算符号，如：运算符号，如：+ +、- -、* *、/

16、/u各种标点符号，如：括号、逗号、冒号、等于号各种标点符号，如：括号、逗号、冒号、等于号u数字数字1 1、2 2、9 9u黑体字符串，如：黑体字符串，如：idid、beginbegin、ifif、thenthenn非终结符号非终结符号u次序靠前的大写字母，如：次序靠前的大写字母，如：A A、B B、C Cu大写字母大写字母S S常用作文法的开始符号常用作文法的开始符号u小写的斜体符号串，如：小写的斜体符号串，如：exprexpr、termterm、factorfactor、stmtstmt14Wensheng Li BUPTn文法符号文法符号u次序靠后的大写字母，如：次序靠后的大写字母，如：X

17、 X、Y Y、Z Zn终结终结符号串符号串u次序靠后的小写字母，如：次序靠后的小写字母，如：u u、v v、z zn文法符号串文法符号串u小写的希腊字母，如：小写的希腊字母，如： 、 、 、 n可以直接用产生式的集合代替四元组来描述文法，可以直接用产生式的集合代替四元组来描述文法，第一个产生式的左部符号是文法的开始符号第一个产生式的左部符号是文法的开始符号。文法书写文法书写约定（续）约定（续）15Wensheng Li BUPT四、推导和短语四、推导和短语例：考虑简单算术表达式的文法考虑简单算术表达式的文法G G： G=(+G=(+，* *，（，），（，），i,Ei,E，T T，F,E,F,E

18、, ) ) ： E E E + T | T E + T | T T T T T * * F | F F | F F F（E E）| i| in文法所产生的语言文法所产生的语言从文法的开始符号出发，反复连续使用产生式对非终结符从文法的开始符号出发，反复连续使用产生式对非终结符号进行替换和展开，就可以得到该文法定义的语言。号进行替换和展开，就可以得到该文法定义的语言。16Wensheng Li BUPT推导推导假定假定A A是一个产生式，是一个产生式， 和和 是任意的文法符号串，是任意的文法符号串，则有：则有： A A n “” 表示表示 “一步一步推导推导”即利用产生式对左边符号串中的一个非终结

19、符号进行替换，即利用产生式对左边符号串中的一个非终结符号进行替换，得到右边的符号串。得到右边的符号串。n 称称 A A 直接推导出直接推导出n 也可以说也可以说是是 A A 的的直接推导直接推导n 或说或说直接归约直接归约到到 A A 17Wensheng Li BUPT 从文法开始符号从文法开始符号E E推导出符号串推导出符号串i+ii+i的详细过程的详细过程如果有直接推导序列：如果有直接推导序列： 1 12 2n n 则说则说 1 1推导出推导出 n n，记作：记作： 1 1 n n * * “ ”“ ”表示表示0 0步或多步推导步或多步推导称这个序列是从称这个序列是从 1 1到到 n n

20、的的长度为长度为n n的推导的推导 A A 所用产生式所用产生式 从从E E到到 的推导长度的推导长度 E E+T E E+T E EE+T 1E+T 1 E+T T+T E+T T+T +T E+T ET 2T 2 T+T F+T T+T F+T +T T+T TF 3F 3 F+T i+T F+T i+T +T F+T Fi 4i 4 i+T i+F i+ i+T i+F i+ T TF 5F 5 i+F i+i i+ i+F i+i i+ F Fi 6i 6E E+T E+T T+T T+T F+T F+T i+T i+T i+F i+F i+ii+i18Wensheng Li BUPT

21、最左推导最左推导最右推导最右推导如果如果 ，并且在每，并且在每“一步推导一步推导”中，都替换中，都替换 中中最左最左边边的非终结符号，则称这样的推导为最左推导。记作：的非终结符号，则称这样的推导为最左推导。记作：* * lm 如果如果 ，并且在每，并且在每“一步推导一步推导”中，都替换中，都替换 中中最右最右边边的非终结符号，则称这样的推导为最右推导。记作：的非终结符号，则称这样的推导为最右推导。记作：* * rm 最右推导也称为最右推导也称为规范推导规范推导E E+T E+T T+T T+T F+T F+T i+T i+T i+F i+F i+ii+iE E+T E+T E+F E+F E+

22、i E+i T+i T+i F+i F+i i+ii+i最左最左推导、最右推导推导、最右推导19Wensheng Li BUPT句型句型句子句子仅含有终结符号的句型是文法的一个仅含有终结符号的句型是文法的一个句子句子。语言语言文法文法G G产生的所有句子组成的集合是文法产生的所有句子组成的集合是文法G G所定义的所定义的语言语言，记作记作L(G)L(G)。对于文法对于文法G=(VG=(VT T,V,VN N,S,S, ) )，如果，如果S S ，则称，则称 是当前文法是当前文法的一个句型。的一个句型。* * 若若S S ，则，则 是当前文法的一个是当前文法的一个左句型左句型，若若S S ，则，

23、则 是当前文法的一个是当前文法的一个右句型右句型。* * lmlm* * rmrmL(G)= L(G)= | S | S ，并且，并且 V VT T* * + + 句型、句子和语言句型、句子和语言20Wensheng Li BUPTn对于文法对于文法G=(VG=(VT T,V,VN N,S,S, ) )，假定，假定是文法是文法G G的一个句型，的一个句型，如果存在：如果存在：短语、直接短语和句柄短语、直接短语和句柄S A ，并且，并且 A * + 则则称称 是句型是句型关于非终结符号关于非终结符号A A的的短语短语。n如果存在：如果存在：S S A A ，并且，并且 A A * 则则称称 是句

24、型是句型关于非终结符号关于非终结符号A A的的直接短语直接短语。n一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄。 例例: :E ET TT T* *F FT T* *(E)(E)F F* *(E)(E)i i* *(E)(E)i i* *(E+T)(E+T)i i* *(T+T)(T+T)i i* *(F+T)(F+T)i i* *(i+T)(i+T) 21Wensheng Li BUPT五、分析树及二义性五、分析树及二义性n分析树分析树n子树子树n子树与短语之间的关系子树与短语之间的关系n二义性二义性22Wensheng Li BUPT分析树分析树n推导的图形

25、表示，又称推导树。推导的图形表示，又称推导树。n一棵一棵有序有向树有序有向树，因此具有树的性质；，因此具有树的性质；n分析树的分析树的特点：每一个结点都有标记。特点：每一个结点都有标记。u根结点由文法的开始符号标记；根结点由文法的开始符号标记；u每个内部结点由非终结符号标记，它的子每个内部结点由非终结符号标记，它的子结点由这个非终结符号的这次推导所用产结点由这个非终结符号的这次推导所用产生式的右部各符号从左到右依次标记；生式的右部各符号从左到右依次标记；u叶结点由非终结符号或终结符号标记，它叶结点由非终结符号或终结符号标记，它们从左到右排列起来，构成句型。们从左到右排列起来，构成句型。 E E

26、T TT T* *F FT T* *(E)(E)F F* *(E)(E)i i* *(E)(E)i i* *(E+T)(E+T)i i* *(T+T)(T+T)i i* *(F+T)(F+T)i i* *( (i+Ti+T) ) E ET TT T* *F FF F* *F Fi i* *F Fi i* *(E)(E)i i* *(E+T)(E+T)i i* *(T+T)(T+T)i i* *(F+T)(F+T)i i* *( (i+Ti+T) ) E T T * F F ( E ) i E + T T F i 23Wensheng Li BUPTT子树子树E子树子树T子树子树 E T T *

27、 F F ( E ) i E + T T F i 子树子树n分析树中一个特有的分析树中一个特有的结点结点、连同它的连同它的全部后裔结点全部后裔结点、连、连接这些结点的接这些结点的边边、以及这些、以及这些结点的结点的标记标记。n子树的根结点的标记可能不子树的根结点的标记可能不是文法的开始符号。是文法的开始符号。n如果子树的根结点标记为非如果子树的根结点标记为非终结符号终结符号A A，则可称该子树，则可称该子树为为A-A-子树子树。24Wensheng Li BUPT短语短语i+T直接直接短语短语 i句柄句柄i E T T * F F ( E ) i E + T T F i 子树与短语的关系子树与

28、短语的关系n一棵一棵子树的所有叶结点子树的所有叶结点自左自左至右排列起来，形成此句型至右排列起来，形成此句型相对于该子树根的相对于该子树根的短语短语；n分析树中分析树中只有父子两代只有父子两代的子的子树的所有叶结点自左至右排树的所有叶结点自左至右排列起来，形成此句型相对于列起来，形成此句型相对于该子树根的该子树根的直接短语直接短语；n分析树中分析树中最左边最左边的那棵只有的那棵只有父子两代的子树的所有叶结父子两代的子树的所有叶结点自左至右排列起来，就是点自左至右排列起来，就是该句型的该句型的句柄句柄。25Wensheng Li BUPT二义性二义性n如果一个文法的某个句子有不止一棵分析如果一个

29、文法的某个句子有不止一棵分析树，则这个句子是树，则这个句子是二义性的义性的。n含有二义性句子的文法是含有二义性句子的文法是二义性的文法义性的文法。例：考虑文法考虑文法 G=(+,G=(+,* *, ,（, ,）,i,E,E,i,E,E, ) ) ： E E E+E | E E+E | E* *E | (E) | E | (E) | id 句子句子 id+idid+id* *id id 存在两个不同的最左推导：存在两个不同的最左推导：E EE+EE+Eid+Eid+Eid+Eid+E* *E Eid+idid+id* *E Eid+idid+id* *ididE EE E* *E EE+EE+E

30、* *E Eid+Eid+E* *E Eid+idid+id* *E Eid+idid+id* *idid有两棵不同的分析树有两棵不同的分析树E E + E E * EidididE E * E E + Eididid26Wensheng Li BUPT文法的二义性和语言的二义性文法的二义性和语言的二义性n如果两个文法产生的语言相同，即如果两个文法产生的语言相同，即L(G)=L(GL(G)=L(G ) )，则称，则称这两个这两个文法是等价文法是等价的。的。n有时，一个二义性的文法可以变换为一个等价的、有时，一个二义性的文法可以变换为一个等价的、无二义性的文法。无二义性的文法。n有些语言，根本就

31、不存在无二义性的文法，这样的有些语言，根本就不存在无二义性的文法，这样的语言称为语言称为二义性的语言二义性的语言。n二义性问题是不可判定的二义性问题是不可判定的u不存在一种算法，它能够在有限的步骤内确切地判定出一不存在一种算法，它能够在有限的步骤内确切地判定出一个文法是否是二义性的。个文法是否是二义性的。u可以找出一些充分条件（未必是必要条件），当文法满足可以找出一些充分条件（未必是必要条件），当文法满足这些条件时，就可以确信该文法是无二义性的。这些条件时，就可以确信该文法是无二义性的。27Wensheng Li BUPT六、文法的变换六、文法的变换n文法二义性的消除文法二义性的消除n左递归的

32、消除左递归的消除n提取左因子提取左因子28Wensheng Li BUPT文法二义性的消除文法二义性的消除n映射程序设计语言中映射程序设计语言中IF语句的文法：语句的文法：stmt if expr then stmt | if expr then stmt else stmt | othern句子句子if E1 then if E2 then S1 else S2有两棵不同有两棵不同的分析树：的分析树：stmtif expr then stmt E1 if expr then stmt else stmtE2 S1 S2stmtif expr then stmt else stmt E1 if

33、 expr then stmt S2E2 S1 29Wensheng Li BUPT利用利用“最近最近最后匹配最后匹配原则原则”else必须匹配离它最近的那个未匹配的必须匹配离它最近的那个未匹配的then。n出现在出现在then和和else之间的语句必须是之间的语句必须是“匹配的匹配的”。n所谓所谓匹配的语句匹配的语句是不包含不匹配语句的是不包含不匹配语句的if-then-else语句，或是其他任何非条件语句。语句，或是其他任何非条件语句。n改写后的文法：改写后的文法：stmtmatched_stmt | unmatched_stmtmatched_stmtif expr then match

34、ed_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt30Wensheng Li BUPT句子句子if Eif E1 1 then if E then if E2 2 then S then S1 1 else S else S2 2的分析树的分析树unmatched_stmtif expr then stmt E1 matched_stmtE2 other other stmtif expr then matched_st

35、mt else matched_stmt S1 S231Wensheng Li BUPT左递归的消除左递归的消除一个文法是一个文法是左递归左递归的，如果它有非终结符号的，如果它有非终结符号A A，对某个，对某个文法符号串文法符号串 ，存在推导：，存在推导：n消除消除直接直接左左递归的方法：递归的方法：简单情况简单情况：如果文法：如果文法G G有产生式：有产生式：A AA A | | 可以把可以把A A的这两个产生式改写为：的这两个产生式改写为：A AA A A AA A | | 这两组产生式是等价的这两组产生式是等价的由于从由于从A A推导出的符号串是相同的，即都是推导出的符号串是相同的，即都

36、是 A AA A + 若存在某个若存在某个 = = ，则称该文法是，则称该文法是有环路的有环路的。32Wensheng Li BUPTn例：消除表达式文法中的左递归例：消除表达式文法中的左递归：EE+T|TTT*F|F F(E)|idn利用利用消除直接左递归的方法，可以改写为消除直接左递归的方法，可以改写为: ETE E+TE | TFT T*FT | F(E) | id示例：消除直接左递归示例：消除直接左递归33Wensheng Li BUPTn一般情况：一般情况：假定假定关于关于A的全部产生式是的全部产生式是： AA 1|A 2|A m| 1| 2| nn产生式可以改写为：产生式可以改写为

37、： A1A | 2A | nA A1A | 2 A | mA | 消除消除直接直接左左递归（续）递归（续）34Wensheng Li BUPTn例如例如有间接左递归文法：有间接左递归文法： SAa|b AAc|Sd| 消除间接消除间接左左递归递归35Wensheng Li BUPT算法：消除左递归消除左递归输入：无环路、无输入：无环路、无 -产生式的文法产生式的文法G输出：不带有左递归的、与输出：不带有左递归的、与G等价的文法等价的文法G方法：方法：(1)把文法把文法G的所有非终结符号按某种顺序排列成的所有非终结符号按某种顺序排列成A1,A2,An(2)for (i=1; i=n; i+) f

38、or (j=1; jn)m(mn)个状态的个状态的DFADFA与之等价。与之等价。nDFA DDFA D的化简的化简，指寻找一个，指寻找一个状态数比较少的状态数比较少的DFA DDFA D ，使，使L(D)=L(DL(D)=L(D ) )。n可以证明，存在一个最少状可以证明，存在一个最少状态的态的DFA DDFA D，使，使L(D)=L(D)L(D)=L(D)，并且这个并且这个DD是唯一的是唯一的。63Wensheng Li BUPTDFA DDFA D的最小化过程的最小化过程定义：定义：设设s,ts,t Q Q，若对任何，若对任何ww* *， (s,(s,w w) ) F F 当且仅当当且仅

39、当 (t,(t,w w) ) F F，则称状态，则称状态s s和和t t是等价的。是等价的。否则称状态否则称状态s s和和t t是可区分的。是可区分的。DFA DDFA D的最小化过程：的最小化过程：n首先，把首先，把D D的状态集合分割成一些互不相交的子集，使每个子的状态集合分割成一些互不相交的子集，使每个子集中的任何两个状态是等价的，而任何两个属于不同子集的集中的任何两个状态是等价的，而任何两个属于不同子集的状态是可区分的。状态是可区分的。n然后，在然后，在每个子集中任取一个状态作每个子集中任取一个状态作“代表代表”，删去该子集，删去该子集中其余的状态，并把射向其它结点的边改为射向中其余的

40、状态，并把射向其它结点的边改为射向“代表代表”结结点。点。n最后，如果最后，如果得到的得到的DFADFA中有死状态、或从初态无法到达的状态，中有死状态、或从初态无法到达的状态，则把它们删除。则把它们删除。64Wensheng Li BUPT把把状态集合状态集合Q Q分割成满足要求的子集分割成满足要求的子集n把状态集合把状态集合Q Q划分成两个子集：终态子集划分成两个子集：终态子集F F和非终态和非终态子集子集G G。n对每个子集进行划分：对每个子集进行划分：u取某个子集取某个子集A=sA=s1 1,s,s2 2, ,s,sk k u取某个输入符号取某个输入符号a a，检查，检查A A中的每个状

41、态对该输入符号的转中的每个状态对该输入符号的转换。换。u如果如果A A中的状态相对于中的状态相对于a a，转换到不同子集中的状态，则要，转换到不同子集中的状态，则要对对A A进行划分。使进行划分。使A A中能够转换到同一子集的状态作为一个中能够转换到同一子集的状态作为一个新的子集。新的子集。u重复上述过程，直到每个子集都不能再划分为止重复上述过程，直到每个子集都不能再划分为止。65Wensheng Li BUPT示例示例：对状态转换图所描述的对状态转换图所描述的DFA DDFA D最小化最小化第一步第一步：把：把DFA DDFA D的状态集的状态集合划分为子集，使合划分为子集，使每个子集中的状

42、态每个子集中的状态相互等价，不同子相互等价，不同子集中的状态可区分。集中的状态可区分。 A开始开始 E C B D abaabaabbbn把把D D的状态集合划分为两个子集：的状态集合划分为两个子集：A,B,C,DA,B,C,D和和EEn考察非终态子集考察非终态子集A,B,C,DA,B,C,D- - 对于对于a a，状态，状态A,B,C,DA,B,C,D都转换到状态都转换到状态B B，所以对输入符号，所以对输入符号a a而言，该子集不能再划分。而言，该子集不能再划分。- - 对于对于b b，状态，状态A,B,CA,B,C都转换到子集都转换到子集A,B,C,DA,B,C,D中的状态，而中的状态，

43、而状态状态D D则转换到子集则转换到子集EE中的状态。中的状态。- - 应把子集应把子集A,B,C,DA,B,C,D划分成两个新的子集划分成两个新的子集A,B,CA,B,C和和DD。66Wensheng Li BUPTD D的状态集合被划分为：的状态集合被划分为：A,B,CA,B,C、DD和和EEn考察子集考察子集A,B,CA,B,C- - 对于对于a a，状态，状态A,B,CA,B,C都转换到状态都转换到状态B B，所以对输入符号，所以对输入符号a a而而言，该子集不能再划分。言，该子集不能再划分。- - 对于对于b b，状态，状态A,CA,C转换到转换到C C，状态，状态B B转换到转换到

44、D D。状态。状态C C和和D D分分属于不同的子集。属于不同的子集。- - 应把子集应把子集A,B,CA,B,C划分成两个新的子集划分成两个新的子集A,CA,C和和BB。D D的状态集合被划分为：的状态集合被划分为：A,CA,C、BB、DD和和EEn考察子集考察子集A,CA,C- - 对于对于a a，状态，状态A,CA,C都转换到状态都转换到状态B B。- - 对于对于b b，状态，状态A,CA,C都转换到状态都转换到状态C C。- - 该子集不可再划分。该子集不可再划分。D D的状态集合最终被划分为：的状态集合最终被划分为：A,CA,C、BB、DD和和EE67Wensheng Li BUP

45、T构造最小构造最小DFA DDFA D n第二步：第二步：为每个子集选择一个代表状态。为每个子集选择一个代表状态。u选择选择A A为子集为子集A,CA,C的代表状态的代表状态nD D 的状态转换图的状态转换图 A开始开始 E D B ababbaabnD D 的状态转换矩阵的状态转换矩阵状态状态 输入符号输入符号 a ba b A B A A B A B B D B B D D B E D B E E B A E B A68Wensheng Li BUPT2.3 2.3 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n如果对于某个正规文法如果对于某个正规文法G G和某个有限自动机和某

46、个有限自动机M M，有，有L(G)=L(M)L(G)=L(M)，则称则称G G和和M M是等价的。是等价的。n定理：对每一个右线性文法对每一个右线性文法G G或左线性文法或左线性文法G G，都存在一个等，都存在一个等价的有限自动机价的有限自动机M M。证明：首先考虑右线性正规文法证明：首先考虑右线性正规文法 设给定的一个右线性文法设给定的一个右线性文法G G为：为：G=(VG=(VT T，V VN N，S S， ) ) 与与G G等价的有限自动机等价的有限自动机M M为：为：M=(M=( ，Q Q，q q0 0，F F， ) ) =V=VT T，q q0 0=S=S，F=fF=f，f f为新增

47、加的一个终态符号，为新增加的一个终态符号，f f V VN N ，Q=VQ=VN Nff 的定义为的定义为：u若文法若文法G G有产生式有产生式A Aa a，其中，其中A A V VN N，a a V VT T ，则，则 (A,a)=f(A,a)=f。u若文法若文法G G有产生式有产生式A AaAaA1 1|aA|aA2 2| |aA|aAk k， 其中其中A,AA,Ai i V VN N,(i=1,2,(i=1,2,k),a,k),a V VT T ，则，则 (A,a)=A(A,a)=A1 1,A,A2 2, ,A,Ak k 。69Wensheng Li BUPTwwL(G)L(G)的的充分

48、必要条件充分必要条件是是wwL(M)L(M)，所以，所以L(G)=L(M)L(G)=L(M)n在正规文法在正规文法G G中，开始符号中，开始符号S S推导出推导出w w的充分必要条件为：在的充分必要条件为：在自动机自动机M M中，从初态中，从初态S S到终态到终态f f有一条路径，该路径上所有边的有一条路径，该路径上所有边的标记依次连接起来恰好是标记依次连接起来恰好是w w。现在考虑左线性正规文法现在考虑左线性正规文法 设给定的一个左线性文法设给定的一个左线性文法G G为：为：G=(VG=(VT T，V VN N，S S， ) ) 与与G G等价的有限自动机等价的有限自动机M M为：为：M M

49、 =(=( ，Q Q，q q0 0，F F， ) ) =V=VT T，F=SF=S，新增加一个初态符号新增加一个初态符号q q0 0，q q0 0 V VN N，Q=VQ=VN Nqq0 0 的定义为的定义为：u若文法若文法G G有产生式有产生式A Aa a，其中，其中A A V VN N，a a V VT T ，则，则 (q(q0 0,a)=A,a)=A。u若文法若文法G G有产生式有产生式A A1 1AaAa，A A2 2AaAa，A Ak kAaAa， 其中其中A,AA,Ai i V VN N,(i=1,2,(i=1,2,k),a,k),a V VT T ，则，则 (A,a)=A(A,a

50、)=A1 1,A,A2 2, ,A,Ak k 可以证明可以证明L(G)=L(ML(G)=L(M ) )，即，即有限自动机有限自动机M M 与左线性文法与左线性文法G G是等价的。是等价的。70Wensheng Li BUPT示例示例：设有右线性文法设有右线性文法G=(G=(a,ba,b, S,B, S, , S,B, S, ) )，其中，其中 ： S SaBaB B BaB|bS|aaB|bS|a 试构造与试构造与G G等价的有限自动机等价的有限自动机M M。n设设FA M=(FA M=( , Q, q, Q, q0 0, F, , F, ) )n =a,b q=a,b q0 0=S F=f

51、Q=S,B,f =S F=f Q=S,B,f n转换函数转换函数 ：u对于产生式对于产生式S SaBaB，有，有 (S,a)=B(S,a)=Bu对于产生式对于产生式B BaBaB，有，有 (B,a)=B(B,a)=Bu对于产生式对于产生式B BbSbS，有，有 (B,b)=S(B,b)=Su对于产生式对于产生式B Ba a， 有有 (B,a)=f(B,a)=fnFA MFA M的状态转换图：的状态转换图：SBf开始开始aaab71Wensheng Li BUPT定理：定理：对每一个对每一个DFA MDFA M，都存在一个等价的右线性文，都存在一个等价的右线性文 法法G G和一个等价的左线性文法

52、和一个等价的左线性文法G G 。设设DFA MDFA M为：为：M=(M=( ，Q Q，q q0 0，F F， ) )n构造右线性文法构造右线性文法G G：G=(VG=(VT T，V VN N，S S， ) ) V VT T= = 、V VN N=Q=Q、S=qS=q0 0 的的构造：对任何构造：对任何a a，及，及A A、B B Q Q，若存在，若存在 (A,a)=B(A,a)=B，则：，则：u如果如果B B F F，则有，则有A AaBaBu如果如果B B F F，则有，则有A AaB|aaB|an证明证明L(M)L(M)= =L(G)L(G) 首先证明被首先证明被DFA MDFA M接受

53、的语言可以由右线性文法接受的语言可以由右线性文法G G产生产生 对任何对任何wwL(M),L(M),设设w w=a=a1 1a a2 2aan n，a ai i，存在，存在状态序列状态序列：q q0 0,q,q1 1,q,qn-1n-1,q,q q q F F，有，有转换函数转换函数 (q(q0 0,a,a1 1)=q)=q1 1， (q(q1 1,a,a2 2)=q)=q2 2， (q(qn-1n-1,a,an n)=q)=q 因此在文法因此在文法G G中有中有产生式产生式：q q0 0a a1 1q q1 1, q, q1 1a a2 2q q2 2, , q, qn-1n-1a an n

54、 于是有于是有推导序列推导序列：q q0 0a a1 1q q1 1a a1 1a a2 2q q2 2a a1 1a a2 2a an-1n-1q qn-1n-1a a1 1a a2 2a an n 因此，因此，a a1 1a a2 2a an n是文法是文法G G生成的一个句子生成的一个句子，即，即wwL(G)L(G)，因此因此L(M)L(M) L(G)L(G)72Wensheng Li BUPT 再证明由文法再证明由文法G G产生的语言，能够被产生的语言，能够被DFA MDFA M所接受。所接受。 对任何对任何wwL(G)L(G)，设设w w=a=a1 1a a2 2a an n，其中，

55、其中a ai i V VT T，必存在，必存在推导序列推导序列： q q0 0a a1 1q q1 1a a1 1a a2 2q q2 2a a1 1a a2 2a an-1n-1q qn-1n-1a a1 1a a2 2a an n DFA M DFA M中有中有转换函数转换函数： (q(q0 0,a,a1 1)=q)=q1 1, , (q(q1 1,a,a2 2)=q)=q2 2, , , (q(qn-1n-1,a,an n)=q,)=q,并且并且q q F F 在在DFA MDFA M中有一条中有一条从从q q0 0出发、依次经过状态出发、依次经过状态q q1 1,q,q2 2, ,q,

56、qn-1n-1再到达终态再到达终态q q的的道路道路，路径上有向边的标记依次为，路径上有向边的标记依次为a a1 1,a,a2 2, ,a,an-1n-1,a,an n，这些标记依次连接，这些标记依次连接起来恰好是起来恰好是w w，所以，所以w w被被DFA MDFA M所接受，即所接受，即wwL(M)L(M)，因此因此L(G)L(G) L(M)L(M)。n若若q q0 0 F F，则，则w w= =L(M)L(M)，但，但L(L(G)G)，即：，即：L(G)=L(M)-L(G)=L(M)- 进一步进一步改进文法改进文法G G：增加一个新的非终结符号：增加一个新的非终结符号S S ，及相应产生

57、，及相应产生式：式：S SS|S| ，并用并用S S 代替代替S S作为文法的开始符号。作为文法的开始符号。 改进后的文法改进后的文法G G仍是右线性文法，并且满足：仍是右线性文法，并且满足：L(M)=L(G)L(M)=L(G)。推论：推论：对任何一个有限自动机对任何一个有限自动机M M，都存在一个等价的，都存在一个等价的 正规文法正规文法G G，反之亦然。，反之亦然。推论：推论：对任何一个右线性文法对任何一个右线性文法G G，都存在一个等价的，都存在一个等价的 左线性文法左线性文法G G ，反之亦然。，反之亦然。73Wensheng Li BUPT示例示例：设有设有DFA M=(DFA M=

58、(a,ba,b, q, q0 0,q,q1 1,q,q2 2,q,q3 3,q,q0 0,q,q3 3, ) ) 其中其中转换函数转换函数 如下：如下： (q(q0 0,a)=q,a)=q1 1, , (q(q1 1,a)=q,a)=q3 3, , (q(q2 2,a)=q,a)=q2 2 (q(q0 0,b)=q,b)=q2 2, , (q(q1 1,b)=q,b)=q1 1, , (q(q2 2,b)=q,b)=q3 3试试构造与之等价的右线性文法构造与之等价的右线性文法G G。nDFA MDFA M的状态转换图的状态转换图q0q1q2q3aaabbb开始开始n构造右线性文法构造右线性文法

59、G=(VG=(VT T,V,VN N,S,S, ) )nV VT T=a,b V=a,b VN N=q=q0 0,q,q1 1,q,q2 2,q,q3 3 S=q S=q0 0n产生式集合产生式集合 (q(q0 0,a)=q,a)=q1 1， q q0 0aqaq1 1 (q(q0 0,b)=q,b)=q2 2， q q0 0bqbq2 2 (q(q1 1,a)=q,a)=q3 3，q q3 3 F F， q q1 1a|aqa|aq3 3 (q(q1 1,b)=q,b)=q1 1， q q1 1bqbq1 1 (q(q2 2,a)=q,a)=q2 2， q q2 2aqaq2 2 (q(q2

60、 2,b)=q,b)=q3 3，q q3 3 F F， q q2 2b|bqb|bq3 3构造的文法构造的文法G G：G=(a,b,qG=(a,b,q0 0,q,q1 1,q,q2 2,q,q0 0, , ) ) ：q q0 0aqaq0 0|bq|bq2 2 q q1 1a|bqa|bq1 1 q q2 2aqaq2 2|b|b74Wensheng Li BUPT2.4 2.4 正规表达式与有限自动机的等价性正规表达式与有限自动机的等价性n用正规表达式可以精确地定义集合，用正规表达式可以精确地定义集合， 定义定义PascalPascal语言标识符的正规表达式：语言标识符的正规表达式： let