西电编译原理_第二章习题解答

1、西安电子科技大学 软件学院编译原理编译原理第二章第二章部分习题解答部分习题解答西安电子科技大学 软件学院第第2章习题章习题1. 1. 根据模式，写出正规式根据模式，写出正规式2. 2. 依据依据 NFA/DFANFA/DFA，写出正规式，写出正规式2难点难点3. 3. 正规式正规式NFANFA4. 4. NFANFADFADFA： _闭包，闭包，smovesmove5. 5. DFADFA最小化最小化计算量大计算量大西安电子科技大学 软件学院1. 根据模式写出正规式根据模式写出正规式一般思路：（一般思路：（1）分析题意）分析题意 （2）列举一些最简单的例子）列举一些最简单的例子 （3）寻找统一

2、规律寻找统一规律*,考虑所有可能情况考虑所有可能情况*习题习题2.4 (1) 由偶数个由偶数个0和奇数个和奇数个1构成的构成的01串串 解：解： 最简单的串有最简单的串有 0个个0和和1个个1组成的串：组成的串： 2个个0和和1个个1组成的串：组成的串： 在上述串的中间、两头添加偶数个在上述串的中间、两头添加偶数个0和和/或偶数个或偶数个1，即可，即可得到满足题意的其他串。得到满足题意的其他串。 设设偶数个偶数个0/偶数个偶数个1组成的串组成的串，可用正规式，可用正规式 A 表示，则最表示，则最终正规式：终正规式： A1A | A0A1A0A 1 010 ，001，100* 关键：关键：如何构

3、造正规式如何构造正规式 A ?3西安电子科技大学 软件学院习题习题2.4 (1) 由偶数个由偶数个0和奇数个和奇数个1构成的构成的01串串 构造正规式构造正规式 A(偶数个偶数个0/偶数个偶数个1) a) 长度为长度为2: 00, 11 长度为长度为4：0011, 1100, 0101, 0110, 1001, 1010 b) 前前4个串：个串： 由由00和和11组成的串组成的串正规式正规式B*, B= 00 | 11 c) 后后4个串：个串： 由由01和和10组成的串组成的串正规式正规式C*, C= 01|10 d) 修改正规式修改正规式C为为D： A = (B*|C*)* = (00 |

4、11|01|10)* 考虑：考虑：0001 D = (01|10) (01|10) (00|11)* 最终最终A = (B|D)* = ( (00|11) | (01|10) (00|11)* (01|10) )*？41. 根据模式写出正规式根据模式写出正规式(1) 分析题意分析题意(2)列举一些最简单的例子列举一些最简单的例子(3)寻找规律寻找规律,考虑所有可能情况考虑所有可能情况西安电子科技大学 软件学院(1) 最简单的串：最简单的串：(2) 上述各串重复：上述各串重复： (0 | 00 | 01 | 010 )* = (01 | 0)*(3) 再考虑：仅由再考虑：仅由1组成的串，或组成的

5、串，或 若干若干1打头的串。打头的串。 最终的正规式：最终的正规式： 习题习题2.4 (2) 所有不含有子串所有不含有子串 011 的的01串串 思路思路1：简单例子，观察规律：简单例子，观察规律51* | 1*(01|0)* = 1*(01|0)*1. 根据模式写出正规式根据模式写出正规式0 , 1, 11, 00, 10, 01, 010, 西安电子科技大学 软件学院 含有含有 子串子串 011 的最简单的串：的最简单的串： 其中插入若干个其中插入若干个0 （注意（注意11之间应至少插入之间应至少插入1个个0），），即可不出现即可不出现“011”， 正规式为：正规式为： (0+1) (0+

6、1) 0* 即：每个即：每个1前面至少前面至少1个个0，正规式化简为：，正规式化简为： (01 | 0)* 再考虑：仅由再考虑：仅由1组成的串，或组成的串，或 若干若干1打头的串。打头的串。 最终的正规式：最终的正规式： 1*(01|0)*0 1 1 习题习题2.4 (2) 所有不含有子串所有不含有子串 011 的的01串串 0*0 0* 0* 0* 思路思路2：考虑包含：考虑包含 011 的串，然后构造没有的串，然后构造没有011的串的串61. 根据模式写出正规式根据模式写出正规式西安电子科技大学 软件学院习题习题2.4 (4) 块注释块注释 /* */ 。其中。其中 中不含有中不含有 子串

7、子串 */ 。思路：简单例子，观察规律。思路：简单例子，观察规律。关键：关键：注释中若出现注释中若出现 * *：若紧跟的是：若紧跟的是/ /则结束注释，则结束注释， 否则仍然是注释。否则仍然是注释。 注释为空：注释为空： 考虑没有考虑没有 * * 的注释：的注释： 考虑含考虑含 * * 的注释：的注释：以上情况以上情况 进行或运算，可得：进行或运算，可得：/* */* * */* (*/)* */ 考虑：中间可有若干连续考虑：中间可有若干连续 * *，可得最终正规式：，可得最终正规式： /* (*|*/)* * */71. 根据模式写出正规式根据模式写出正规式/ /* * ( ( * * |

8、| * */ / ) )* * * */ /* */ / ) )* * * */ /西安电子科技大学 软件学院2.依据依据NFA/DFANFA/DFA，给出正规式，给出正规式思路思路1 1： 回顾回顾“正规式正规式 与与 FAFA的关系的关系” 正规式、正规式、FAFA是从两个不同的侧面表示一个集合是从两个不同的侧面表示一个集合( (即正即正规集规集) )。所以，根本的方法是。所以，根本的方法是以正规集为桥梁以正规集为桥梁，- - 先分析清楚先分析清楚 FA FA 识别的集合之识别的集合之结构特征结构特征，- - 然后再设计此集合的正规式。然后再设计此集合的正规式。8西安电子科技大学 软件学院

9、2.依据依据NFA/DFANFA/DFA，给出正规式，给出正规式思路思路2 2：根据根据FAFA直接写出对应的正规式。其考查重点、步骤直接写出对应的正规式。其考查重点、步骤: :考查考查“FAFA之状态图的结构与正规式运算的关系之状态图的结构与正规式运算的关系”(1) (1) 从同一状态出发的从同一状态出发的 多条边多条边/ /路径：路径：(3) (3) 环：环： (2) (2) 同一个状态的入边同一个状态的入边和和 出边：出边：a | ba | babab然后据上，然后据上，考查每条从初态到终态的路径考查每条从初态到终态的路径，综合正规式即可。，综合正规式即可。重复重复0 0次或多次次或多次

10、： * *，至少重复，至少重复1 1次：次： + +9西安电子科技大学 软件学院2.依据依据NFA/DFANFA/DFA，给出正规式，给出正规式习题习题2.10 (2) 用正规式描述用正规式描述 DFA 所接受的语言；所接受的语言； 该该DFADFA从初态到终态有三条路径：从初态到终态有三条路径：0 0b b2 2，0 0c c2 2，0 0a a1 1b b2 2 用正规式表示为：用正规式表示为： b b | | c c | | a(a|c) a(a|c)* *b b，而且是这三条路径均而且是这三条路径均至少重复至少重复一次，一次，故最终的正规式为：故最终的正规式为：(b(b| |c c|

11、|a(a|c)a(a|c)* *b)b)+ +10西安电子科技大学 软件学院其它其它11习题习题2.9 用自然语言给出下述正规式所描述的语言，并构造他们的最小DFA： 10*1(0|1)*011(0|1)*说明：所谓用自然语言描述就是解释字符串的特点。注意：绝对不允许用正规式表示，因为正规式是已知条件.解：10*1：首尾是1、中间有零或若干个0的01串。(0|1)*011(0|1)* ：至少含一个011的01串。西安电子科技大学 软件学院其它其它12关于：正规式 - NFA - DFA - DFA最小化：说明：（一般）逐步计算正规式-NFA：（1）呆板Thompson算法: 自上而下分解正规式

12、 语法树， 自下而上构造NFA 后续遍历;特点：每个运算对应一次构造，繁琐！（2）活用Thompson算法： 分解正规式：得到若干规模适中的子正规式； 为每个子正规式：画出其最简的状态转换图（子图）； 按Thompson算法，将子图组合，得到完整的图。西安电子科技大学 软件学院其它其它13关于：正规式 - NFA - DFA - DFA最小化：说明：（一般）逐步计算NFA-DFA（子集法）：关键点: (1) _闭包（闭包（NFANFA初态初态 ）, , 即即DFADFA的初态；的初态； (2) 计算计算 DFADFA的状态转移（同时得到的状态转移（同时得到DFADFA的其它状态）；的其它状态）； * * * 借助借助状态转换矩阵状态转换矩阵登记：登记：DFADFA状态、状态转移。状态、状态转移。 (3) DFA DFA终态：包含终态：包含NFANFA终态的状态集。终态的状态集。DFA最小化：关键点: (1) 初始划分：终态组，非终态组； (2) 结合状态转换矩阵，分裂每个状态组； (