1、Principles of Compiler第三章 正则语言第三章第三章 正则语言正则语言l 正则语言(Regular Language)一种最简单的形式语言。计算机程序设计语言的词法属于正则语言的范畴。l 本章内容：正则语言的三种模型 有穷状态自动机 正则表达式 正则文法3.1 有穷状态自动机有穷状态自动机l一个识别=a,1 中所有标识符的程序：int nStatus=0;while(ch=getch()if(nStatus=0)if(ch=a)nStatus=1;else return ERROR;else if(ch!=a&ch!=1)return ERROR;return 0;3.1
2、有穷状态自动机有穷状态自动机l识别算法可以用图形表示：3.1 有穷状态自动机有穷状态自动机l 有穷状态自动机(Finite Automata)一台只有一个变量的计算机。变量的取值范围有限，变量的一个值称为该计算机的状态。计算机从初始状态开始运行，从坐向右读入输入的字符。每读一个字符，根据一定规则修改状态值。如果输入结束，当前状态为接受状态，则接受输入的串；否则拒绝输入串。3.1 有穷状态自动机有穷状态自动机lFA的表示方法-状态图：状态：用圆圈表示，圆圈中符号标识状态迁移：用连接两个状态的箭头表示，箭头上的符号为迁移的激活符号初始状态：无源的箭头标识初始状态接受状态：用双圈表示接受状态3.1
3、有穷状态自动机有穷状态自动机lFA的表示方法-迁移表：a101111FA的语法的语法l一台FA M=(Q,q0,F)，其中：Q为一个非空有穷的状态集合；为有穷的字母表(符号集)；：Q Q为状态迁移函数；q0 Q为初始状态；F Q为接受状态集合。3.1 有穷状态自动机有穷状态自动机l M=(Q,q0,F)，其中：Q=0,1；=a,1 ；=(0,a),1),(1,a),1),(1,1),1)；q0=0；F=1。FA的语义的语义(FA与语言的关系与语言的关系)lFA的运行：给定一台FA M=(Q,q0,F)M的一个运行是一个有穷的状态序列=s0s1sn，其中：s0=q0；sn F；0in(a(si,
4、a)=si+1)。l例：01，011，0111都是图中自动机的运行。FA的语义的语义(FA与语言的关系与语言的关系)lFA接受（识别）的串：给定一台FA M=(Q,q0,F)称一个串=a1a2an被M接受（识别），如果M存在一个运行=s0s1sn，使得：0in(si,ai+1)=si+1)。如果串不被M接受，则称M拒绝。lFA M的语言L(M)为所有M接受的串的集合。FA的语义的语义(FA与语言的关系与语言的关系)l例：FA与正则语言与正则语言l定义：称FA M识别语言L，如果M恰好接受L中的所有串。l定义：一个语言是正则的，当且仅当存在一台FA识别它。3.2 正则语言的封闭性正则语言的封闭性
5、l 正则语言在并运算下的封闭性l 定理：如果L1与L2为正则语言，则L1L2也是正则语言。证明思路：构造一台FA恰好识别L1L2。l语言的性质 语言是符号串的集合 补运算l封闭性 如果语言A为正则语言，那么A的补集也是正则语言 语言封闭性的意义3.2.3 正则语言的补运算正则语言的补运算全集为*，即所有可能的符号串的集合。证明思路证明思路l 由于A为正则语言所以存在一台DFA M恰好识别Al 根据M，构造一台DFA M，恰好识别A的补集 对任何一个符号串，如果M接受，则M拒绝 如果M拒绝，则M接受l 证明L(M)=A的补集例：一个正则语言的补集例：一个正则语言的补集10A 所有以开头的串10A
6、 所有不以开头的串MM0()11()MMLL01补自动机的构造补自动机的构造l原始自动机0(,)MQqFl 补自动机0(,)MQqF QQZ 00qq(,),(,)(,)aZ a Zs t Qas a ts a Z FQ FZ证明证明l证明方法()=()MML LL L*()()()()MMMM LLLLl引理1*()()MM LL12.,()naaaM令L0100+1+1,.=0(,)=)nniiiMs sssqsFi ns as 不存在的运行使得12001nnaaaqsssF 1nsF情况:12(0(,)kkkk nt Q s at 情况:12001()nnaaaqsssFM 存在L121
7、00()kkknZZaaaqssaFM 存在Ll在FA的计算过程中，有的时候需要“猜测”的功能 例：证明正则语言在乘积运算下封闭l普通的FA无法“猜测”l需要一种机制能够同时计算所有的可能-非确定性3.3 非确定性的有穷自动机非确定性的有穷自动机lNFA(Nondeterministic Finite Automata)lDFA(Deterministic Finite Automata)lNFA与DFA的区别 从DFA的每一个状态出发，对于字母表中的每一个符号，最多只有一条迁移，而NFA可以有多条。NFA允许“空转移”，也就是能够不读入任何符号就迁移到另外的状态。3.3 非确定性的有穷自动机
8、非确定性的有穷自动机3.3 非确定性的有穷自动机非确定性的有穷自动机对同样的符号有多条迁移允许空转移3.3 非确定性的有穷自动机非确定性的有穷自动机lNFA的计算方式 每当遇到多种选择的时候就分裂，并发计算这些选择。当输入结束的时候，只要有一个分支接受，则接受。l例：输入为1011l一台NFA M=(Q,q0,F)，其中：Q为一个非空有穷的状态集合；为有穷的字母表(符号集)；：Q 2Q为状态迁移函数，其中=；q0 Q为初始状态；F Q为接受状态集合。3.3.1 NFA的形式定义的形式定义3.3.1 NFA的形式定义的形式定义l表格表示方法01q1q1q1,q2q2q3q3q3q4q4q4q4l
9、NFA的运行：M的一个运行是一个有穷的状态序列=s0s1sn，其中：s0=q0；sn F；0in(a(si+1 (si,a)。3.3.2 NFA的语言的语言lNFA接受的串：称一个串=a1a2am被M接受（识别），如果存在一个串=a1a2an，其中a1,a2,an，使得=，而且M存在一个运行=s0s1sn，使得：0in(si+1 (si,ai+1)。如果串不被M接受，则称M拒绝。l例：0111可以写为01113.3.2 NFA的语言的语言lNFA M的语言L(M)为所有M接受的串的集合。3.3.2 NFA的语言的语言l定义：如果两台自动机识别相同的语言，则称这两台自动机等价。l定理：对于任意一
10、台NFA，都存在等价的DFA。l证明思路：对任意的NFA，构造一台DFA，模拟NFA的运行，用DFA的一个状态去记录所有分支的状态。3.3.3 NFA与与DFA的等价性的等价性3.3.3 NFA与与DFA的等价性的等价性l例：l证明：首先不考虑空转移的情况 令NFA N=(Q,q0,F)构造DFA M=(Q,q0,F)，其中 Q=2Q 对所有q Q，a，令(q,a)=rq(r,a)q0=q0 F=q Q|q包含N的一个接受状态 3.3.3 NFA与与DFA的等价性的等价性l考虑空转移的情况l定义函数-Closure 对M的一个状态q Q，-Closure(q)表示从q中的状态出发，只经过空转移
11、能到达的所有状态的集合l改写转移函数：(q,a)=qQ|存在r q，使得q -Closure(r,a)。l改写起始状态 q0=-Closure(q0)3.3.3 NFA与与DFA的等价性的等价性l子集法 构造状态集的幂集，作为DFA的状态集；对DFA的每一个状态，构造由其出发的迁移。l造表法(On-the-fly)首先构造DFA的初始状态；对于现有DFA的状态，构造由其出发的迁移，如果迁移的目标为新状态则构造一个新的状态。3.3.4 从从NFA到到DFA的转换的转换l例：3.3.4 从从NFA到到DFA的转换的转换l推论：一个语言是正则的，当且仅当存在一台NFA识别它。l定理：正则语言在并运算
12、、乘积运算、闭包运算下封闭。3.3.5 正则语言的封闭性正则语言的封闭性l并运算3.3.5 正则语言的封闭性正则语言的封闭性l乘积运算3.3.5 正则语言的封闭性正则语言的封闭性l闭包运算3.3.5 正则语言的封闭性正则语言的封闭性l利用运算符来构造语言运算的表达式，从而得到复杂的语言。l如果这些运算符为正则运算，则称这样的表达式为正则表达式。l正则运算：并、乘积、闭包。3.4 正则表达式正则表达式l语法：归纳定义l称R为一个正则表达式，如果R为以下情况的一种：a，a R1|R2，R1 R2，如果R1与R2都是正则表达式 R1 R2，如果R1与R2都是正则表达式 R1*，如果R1是正则表达式3
13、.4.1 正则表达式的定义正则表达式的定义l语义：归纳定义l如果R为一个正则表达式，那么R的语言L(R)可以归纳定义如下：L(a)=a L()=L()=L(R1|R2)=L(R1)L(R2)L(R1 R2)=L(R1)L(R2)L(R1*)=L(R1)*3.4.1 正则表达式的定义正则表达式的定义lR1|R2=R2|R1 l(R1 R2)R3=R1 (R2 R3)l(R1 R2)R3=R1 (R2 R3)lR1 (R2 R3)=(R1 R2)(R1 R3)3.4.2 正则表达式的性质正则表达式的性质l定理：一个语言是正则的，当且仅当存在一个正则表达式描述它。l引理1：如果一个语言可以用正则表达
14、式描述，则它是正则语言。l引理2：如果一个语言是正则的，那么可以用正则表达式描述它。3.4.3 正则表达式与正则表达式与FA的等价的等价l引理1：如果一个语言可以用正则表达式描述，则它是正则语言。l证明思路：对任意一个正则表达式，都存在等价的FA。l证明方法：归纳法，按照正则运算的次数归纳 归纳基础：运算次数n=0；归纳假设：假设运算次数n 0；|p。l证明思路：令DFA M识别L，p为M的状态数。的长度大于等于p，对应的运行=s0s1sm，满足m p，因此中存在重复的状态。3.7 附录：正则语言的泵引理附录：正则语言的泵引理令k为使得 中状态发生重复的最小下标，=s0s1sjsksm，sj=sk l例：L1=0n1n|n 0 不是正则语言l证明：假设L1是正则语言，那么必然存在泵长度p 选择串=0p1p，将分为三段，考虑以下情况：只包含0：m中0比1多只包含1：m中1比0多包含0与1：m中0与1的次序混乱。所以0p1p不能分割，与假设矛盾，即证。3.7 附录：正则语言的泵引理附录：正则语言的泵引理
