第三章 正则语言

1、Principles of Compiler l第三章 正则语言 第三章第三章 正则语言正则语言 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( c

2、h != a return 0; 3.1 有穷状态自动机有穷状态自动机 l识别算法可以用图形表示： 3.1 有穷状态自动机有穷状态自动机 l 有穷状态自动机( Finite Automata ) 一台只有一个变量的计算机。 变量的取值范围有限，变量的一个值称为该计算机 的状态。 计算机从初始状态开始运行，从坐向右读入输入的 字符。 每读一个字符，根据一定规则修改状态值。 如果输入结束，当前状态为接受状态，则接受输入 的串；否则拒绝输入串。 3.1 有穷状态自动机有穷状态自动机 lFA的表示方法-状态图： 状态：用圆圈表 示，圆圈中符号 标识状态 迁移：用连接两 个状态的箭头表 示，箭头上的符

3、号为迁移的激活 符号 初始状态：无源 的箭头标识初始 状态 接受状态：用双 圈表示接受状态 3.1 有穷状态自动机有穷状态自动机 lFA的表示方法-迁移表： a1 01 111 FA的语法的语法 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)；

4、q0 = 0； F = 1 。 FA的语义的语义( FA与语言的关系与语言的关系 ) lFA的运行： 给定一台FA M = ( Q, , , q0, F ) M的一个运行是一个有穷的状态序列 = s0s1sn， 其中： s0 = q0； sn F； 0in( a( (si, a) = si+1 ) )。 l例： 01，011，0111都是图中自动机的运行。 FA的语义的语义( FA与语言的关系与语言的关系 ) lFA接受（识别）的串： 给定一台FA M = ( Q, , , q0, F ) 称一个串 = a1a2an被M接受（识别），如果M存 在一个运行 = s0s1sn，使得： 0in(si

5、, 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 正则语言的封闭性正则语言的封闭性 l 正则语言在并运算下的封闭性 l 定理：如果L1与L2为正则语言，则L1L2也是正则 语言。 证明思路：构造一台FA恰好识别L1L2。 l语言的性质 语言是符号串的集合 补运算 l封闭性 如果语言A为正则语言，那么A的补集也是正

6、则语言 语言封闭性的意义 3.2.3 正则语言的补运算正则语言的补运算 全集为*，即所有可能的 符号串的集合。 证明思路证明思路 l 由于A为正则语言所以存在一台DFA M恰好识别A l 根据M，构造一台DFA M，恰好识别A的补集 对任何一个符号串，如果M接受，则M拒绝 如果M拒绝，则M接受 l 证明L(M) = A的补集 例：一个正则语言的补集例：一个正则语言的补集 10A 所有以开头的串10A 所有不以开头的串 MM 0() 11() M M L L 01 补自动机的构造补自动机的构造 l原始自动机 0 ( , , , , )MQqF l 补自动机 0 ( , , , , )MQqF Q

7、QZ 00 qq ( , , ) ,( , , ) ( , , ) aZ a Z s t Qas a t s a Z FQ FZ 证明证明 l证明方法 ()=()MML LL L *( ()() ()()MMMM LLLL l引理1 *( ()()MM LL 12. , () n aaaM令L 0100 +1+1 , ,.= 0 ( ( ,)=) nn iii Ms sssqsF i ns as 不存在的运行使得 12 001 n n aaa qsssF 1 n sF情况: 1 2(0( , ) kk kk nt Q s at 情况 : 12 001 () n n aaa qsssF M 存在

8、 L 12 1 00 () kk k n Z Z aaa qss a F M 存在 L l在FA的计算过程中，有的时候需要“猜测”的功 能 例：证明正则语言在乘积运算下封闭 l普通的FA无法“猜测” l需要一种机制能够同时计算所有的可能-非确定性 3.3 非确定性的有穷自动机非确定性的有穷自动机 lNFA( Nondeterministic Finite Automata ) lDFA( Deterministic Finite Automata ) lNFA与DFA的区别 从DFA的每一个状态出发，对于字母表中的每一个 符号，最多只有一条迁移，而NFA可以有多条。 NFA允许“空转移”，也就

9、是能够不读入任何符号 就迁移到另外的状态。 3.3 非确定性的有穷自动机非确定性的有穷自动机 3.3 非确定性的有穷自动机非确定性的有穷自动机 对同样的符号有多条迁移 允许空转移 3.3 非确定性的有穷自动机非确定性的有穷自动机 lNFA的计算方式 每当遇到多种选择的 时候就分裂，并发计 算这些选择。 当输入结束的时候， 只要有一个分支接受， 则接受。 l例： 输入为1011 l一台NFA M = ( Q, , , q0, F )，其中： Q为一个非空有穷的状态集合； 为有穷的字母表( 符号集 )； ：Q 2Q为状态迁移函数，其中=； q0 Q为初始状态； F Q为接受状态集合。 3.3.1

10、NFA的形式定义的形式定义 3.3.1 NFA的形式定义的形式定义 l表格表示方法 01 q1q1q1,q2 q2q3q3 q3q4 q4q4q4 lNFA的运行： 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

11、例： 0111可以写为0111 3.3.2 NFA的语言的语言 lNFA M的语言L(M)为所有M接受的串的集合。 3.3.2 NFA的语言的语言 l定义：如果两台自动机识别相同的语言，则称这 两台自动机等价。 l定理：对于任意一台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,

12、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中 的状态出发，只经过空转移能到达的所有状态的集 合 l改写转移函数： (q,a) = qQ | 存在r q，使得q - Closure(r,a) 。 l改写起始状态 q0 = -Closure(q0) 3.3.3 NFA与与DFA的等价性的等价性 l子集法 构造状态集的幂集，作为DFA的状态集； 对DFA的

13、每一个状态，构造由其出发的迁移。 l造表法( On-the-fly ) 首先构造DFA的初始状态； 对于现有DFA的状态，构造由其出发的迁移，如果 迁移的目标为新状态则构造一个新的状态。 3.3.4 从从NFA到到DFA的转换的转换 l例： 3.3.4 从从NFA到到DFA的转换的转换 l推论： 一个语言是正则的，当且仅当存在一台NFA识别它。 l定理： 正则语言在并运算、乘积运算、闭包运算下封闭。 3.3.5 正则语言的封闭性正则语言的封闭性 l并运算 3.3.5 正则语言的封闭性正则语言的封闭性 l乘积运算 3.3.5 正则语言的封闭性正则语言的封闭性 l闭包运算 3.3.5 正则语言的封

14、闭性正则语言的封闭性 l利用运算符来构造语言运算的表达式，从而得到 复杂的语言。 l如果这些运算符为正则运算，则称这样的表达式 为正则表达式。 l正则运算：并、乘积、闭包。 3.4 正则表达式正则表达式 l语法：归纳定义 l称R为一个正则表达式，如果R为以下情况的一种： a，a R1 | R2，R1 R2，如果R1与R2都是正则表达式 R1 R2，如果R1与R2都是正则表达式 R1*，如果R1是正则表达式 3.4.1 正则表达式的定义正则表达式的定义 l语义：归纳定义 l如果R为一个正则表达式，那么R的语言L(R)可以 归纳定义如下： L(a) = a L() = L() = L(R1 | R

15、2) = 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：如果一个语言可以用正则表达式描述，则 它是正则语言。 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，因此