编译原理：第2章 形式语言与自动机基础3

1、第 2 章 形式语言与自动机基础2.1 文法和语言2.2 有限自动机2.3 正规式与有限自动机Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3 正规式与有限状态自动机 2.3.1 有限自动机与正则文法 2.3.2 正规式与正规集 2.3.3 正规式与FA的等价 Ch2 形式语言自动机理论基础 2.3 正规式与自动机 第 2 章 形式语言与自动机基础43型文法（正则文法、线性文法） 定义2.23： 设文法G=(VN,VT, S, P)，若P中的每个产生式形如 AB或A则称文法G为右线性文法若P中的每个产生式形如： AB 或 A则称文法G为左线性文法其中，A，B VN，VT*，右线性

2、文法和左线性文法统称为3型文法。（正则文法或线性文法）。 Ch2 形式语言自动机理论基础 2.1 文法和语言 2.1.5 文法和语言的类型VT，乔姆斯基范式Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 有限自动机与正则文法 定理2.2 设文法G=(VN, VT, S, P)为一右线性文法(左线性文法结论相同)，则存在一有限自动机M=（Q, , f, q0, Z），使得：L(M)=L(G) 构造有限自动机（1） = VT（2） q0 = S （3） Q = VN qz， qz为一附加状态且qz VN（4）Z= qz（5）f:若P中有产生式B a， 则qz f(B,a) 若P

3、中有产生式B aC，则Cf(B,a) aVTCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 有限自动机与正则文法例：写出与下述文法等价的有限自动机M SaA|bB|A aB|bAB aS|bA|SABqzababab 2.3 正规式与有限状态自动机 2.3.1 有限自动机与正则文法 2.3.2 正规式与正规集 2.3.3 正规式与FA的等价 Ch2 形式语言自动机理论基础 2.3 正规式与自动机 第 2 章 形式语言与自动机基础Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 正规式与正规集 定义2.31 (正规式与正规集) 设为有限字母表，在上的正规式与

4、正规集可递 归定义如下：1. 和是上的正规式，它们表示的正规集分别 为和；2.对任何a,a是上的正规式,它表示的正规集为a；3. 若r,s都是正规式 , 对应的正规集分别为R和S , 则 (r|s)、(rs)、(r)*也是正规式，它们表示的正 规集分别是：RS，RS，R*。4. 有限次使用上述三条规则构成的表达式，称为上 的正规式，仅由这些正规式表示的集合为正规集。Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 正规式与正规集 说明： 1. 正规式与相应的正规集是等价的，正规集给出了 相应正规式所描述的全部单词（句子）； 2. 正规式的运算结果是正规集； 3. 正规式不是集

5、合，其运算结果正规集是集合。 是特例。 4. 运算符可省略。 注意： 1. 正规式运算优先级从高到低 “ （）、*、| ” ； 2. 同级运算从左到右；Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 正规式与正规集例2.32： 令 = 0, 1 则 0，1，和都是上的正规式 ；正规式正规集0 | 1 0，1 0 1 01 1 0 10 0* , 0, 00, 000, 1* , 1, 11, 111, ( 0|1)0* 0, 00,000, 1, 10,100,1000, ( 0|1)01 001, 101 Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1

6、 正规式与正规集例2.33： 令 = A，B，0，1 V=( A | B)( A | B | 0 | 1)*L(V) = “标识符 ” V=( 0 | 1)( 0 | 1)*L(V) = 二进制数字串 正规式r所表示的正规集R是字母表上的语言， 称为正则语言，用 L(r)表示，即R=L(r)。L(r)中的元 素为字符串，称为 L(r)的句子。 若两个正规式r和s所表示的语言 L(r)=L(s)，则称 r, s等价，记为 r=s。例如，1(01)*=(10)*1Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 正规式与正规集例2.34：令 =，.，d，E ，d代表数字。可带符号

7、或不带符号的整数的正规式表示：r =( +|-| )浮点数的正规式表示：r =( +|-|)dd*(dd*.d* | d*.dd* )(| (E (+|-|)dd* )Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.1 正规式与正规集例2.35： 设PASCAL语言子集有如下单词 BEGIN END IF THEN ELSE 标识符 无符号整常数 = = = 正规式描述： 关键字 BEGIN | END | IF | THEN | ELSE 标识符 ( | )* 无符号整常数 ()* 关系运算符 | = | | = | = | Ch2 形式语言自动机理论基础 2.3 正规式与自

8、动机 2.3.1 正规式与正规集 正规式的代数性质 公 理 描 述 s | t = t | s | 是可交换的 s | (t |r) = (s | t) | r | 是可结合的 (s t)r = s (t r) 连接是可结合的 s (t | r) = s t | s r (t | r) s = t s | r s s = s (s= s) 是连接的恒等元素 s* = (s |)* *和间的关系 a* * =a * *是幂等的连接对 | 可分配 2.3 正规式与有限状态自动机 2.3.1 有限自动机与正则文法 2.3.2 正规式与正规集 2.3.3 正规式与FA的等价 Ch2 形式语言自动机理论

9、基础 2.3 正规式与自动机 第 2 章 形式语言与自动机基础Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 定理2.2 字母表上的有限自动机M所接受的语言 L(M)是上的一个正规集； 对于上的每一个正规式 r，存在一个上的有限自动机M，使得：L(M)=L(r)。 上的单词集V *是正规的，当且仅当存在上的FA M，使得V=L(M)。Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 转换方法： 1. 若有上的FA M，构造正规式V使L(M) = L(V)； 2. 上任何正规式V，构造相应的FA M，使得 L(M) = L(V)。

10、 1） 增加结点 qS ，并从 qS 引弧到达q0； 2） 增加结点 qZ ，并从Z中所有状态引弧 到达 qZ ； step1: 将FA M进行拓广； 若有上的FA M，构造正规式V，使L(M) = L(V)；拓广FA的初态拓广FA的唯一终态Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA例2.36: 有NFA M 如下图所示。qZqS4213bbaa0a,ba,ba,bCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAstep2: 利用如下替换规则一逐步消去 M中的结和弧，并用正规式代替原来M中的弧标记，直至只剩下 qS qZ 结

11、为止。两状态弧上标记的正规式即为所求结果。R1R2ABR1|R2ABR1R2* R3ABR1ACR2BR2R1ABR2R1ACR3B替换为替换为替换为 (1) (2) (3)替 换 规 则 一Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 用规则(1)消去1结和3结qZ124bbaaa,ba,bqSa,bqZqS4213bbaa0a,ba,ba,bCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 用规则(3)消去2,4结qZ124bbaaa,ba,bqSa,bqZ0qSa,bbb(a|b)*aa(a|b)*Ch2 形式语言自动机

12、理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 用规则(2)消去0结与qZ结间的一条弧qZ0qSa,bbb(a|b)*aa(a|b)*qZqSbb(a|b)*|aa(a|b)*0a,bCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 用规则(3)消去0结用分配率实施化简VqZqSbb(a|b)*|aa(a|b)*0a,bqZqS(a|b)*(bb|aa)(a|b)*qZqS(bb|aa ) (a|b)*0a,b例2.36: 有FA M 如下图所示。0baa,cbbccCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA写出

13、与其语言等价的正规式r。21012baa,cbbccaabacCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA012baa,cbbccqsqz01ba,cbcqsqza01ba,cbcqsqzabacCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAa | 01ba|cb|abqsqzac|ca | 01ba|c(a|)bqsqz(a|)cb(a|)b)*(a|)b(a|)b)*(a|)cCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA0a|cqsqza|01ba|c(a|)bqsqz(a|)c0qs

14、qzb(a|)b)*(a|)|(b(a|)b)*(a|)|)c|a(b|ba)*c|a)*(b|ba)*正规式r(b|ba)*c|a)*(b|ba)*Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAqsqz0qsqz(b|ba)*(b|ba)*c|a0qsqzb(a|)b)*(a|)|(b(a|)b)*(a|)|)c|aCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA 注意 : (对消弧、消结过程) 实际是正规式的连接运算过程2 ： 上任何正规式V，存在相应的DFA M，使得 L(M) = L(V)。 step1: 由V直接形成拓

15、广的FA状态图。其中，只有开始状态qS和终止状态qZ，连接qS和qZ的有向弧上是正规式V。若所有弧上标记是或上的字符ai, 则构造完成。 若1）不成立，则标记具有R1|R2，R1R2，(R1)*形 式，按照如下替换规则二分解；Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAaiqSqZqSqZ(1)R1R1|R2ABR2AB替换为R1*ABR1ACB替换为R1ACR2BR1R2AB替换为替换规则二Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA3） 对新产生的弧标记重复1）、2），直到没有新的弧和结产生为止。得到V相应的NFA M

16、，且L(M)=L(V)。Step2: NFA M确定化及最小化。Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA例2.36: 有V= (a|b)*(aa|bb)(a|b)* 最小 DFA MqZqS(a|b)*(aa|bb)(a|b)*qZqSaa|bb12(a|b)*(a|b)*qZqS(aa|bb)1256a,ba,bCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAqZqS(aa|bb)1256a,ba,bqZqSaa1256a,ba,bbbqZqS1256a,ba,b34aabbNFA MCh2 形式语言自动机理论基础 2.

17、3 正规式与自动机 2.3.2 正规式与FAI Ia IbqS, 5, 15,1 , 35, 1,4 5, 1, 3 5, 1,4 5, 1, 3,2,6,qZ 5, 1, 3 5, 1, 3,2,6, qZ 5, 1, 4 5,1, 4,2,6, qZ 5,1,4 ,2,6, qZ 5,1, 4,6, qZ 5, 1, 3,2,6, qZ 5,1,4 ,6, qZ 5,1, 3,6, qZ 5,1,3 ,6, qZ 5,1,4 ,2,6, qZ 5,1,3 ,6, qZ 5,1,4 ,2,6, qZ 012 3* 4* 5* 6*13136632245445 M确定化5, 1,3 ,2,6,

18、 qZ 5,1, 4,6, qZ aqZqS1256a,ba,b34abbCh2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAstate a b 012 3* 4* 5* 6*13136632245445DFA M基本划分00,1,2,3,4,5,6考察子集0,1,2，0,2和1被a区分，子集0,1,2应再划分为0,2,1。考察子集3,4,5,6,等价。得新划分1 3,4,5,6,0,2,1 最 小 化Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAstate a b 012 3* 4* 5* 6*13136632245445DFA

19、M基本划分1 3,4,5,6,0,2,1 考察子集0, 2， 0和2被b区分，子集0, 2应再划分为0,2。考察子集3,4,5,6,等价。2已是最后划分。得新划分2 3,4,5,6,1,0,2 最 小 化Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FAstate a b 012 3* 13132233最简DFA Mstate a b 012 3* 4* 5* 6*13136632245445DFA M划分23,4,5,6,0,1,2每个子集中状态都等价。3012Ch2 形式语言与自动机理论基础 第二章第三节提要 2.3.2 正规式与正规集 正规式的描述，正规集的

20、描述 ，用正规式或正规集描述正则语言。 2.3.3 正规式与FA的等价 等价转化算法。 规则（一）和规则（二）。 2.3.1 正则文法与FA的等价 正则文法到FA的转换Ch2 形式语言与自动机理论基础 第二章理论综述四类文法中的3型文法。3型文法定义的语言可用正规式描述，为正则语言。FA描述的语言可用正规式描述，FA作为正则语言识别机制。正则语言的三种描述：正规式、FA、正则文法（3型文法）。 end 第二章 ch2 形式语言自动机理论基础10、设字母表=a,b，给出上的正则式：R=(a|ba)*1)、构造NFA M，使得L(M)=L(R)。2)、将上面的NFA M确定化为DFA M，使得L(M)=L(M)。要求给出确定化的过程。3)、将上面的DFA M最小化为DFA M，使得L(M)=L(M)。要求给出最小化的过程。 ch2 形式语言自动机理论基础 ch2 形式语言自动机理论基础设有某类单词的词法规则为：S aA | bS A a | b 试为识别该类单词的词法分析器构造最简的DFA(用状态转换图表示)。要求：本题构造步骤是按照词法规则先构造识别各类单词的FA，合并后为一个识别该词法表示的所有单词的NFA M，由M得到最简的DFA（给出M的确定化和最小化过程）。 ch2 形式语言自动机理论基础一部文法G的文法符号不是VN就是VT。BN