2022年编译原理分知识点习题词法分析与有穷自动机.docx

《2022年编译原理分知识点习题词法分析与有穷自动机.docx》由会员分享，可在线阅读，更多相关《2022年编译原理分知识点习题词法分析与有穷自动机.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点1. 将图 1 所示的有穷自动机转换成与其等价的正规文法,其中4、5 为终止状态.解答：此题考查有穷自动机到正规文法的转换方法.这类题只需要书中所介绍的方法进行即可得到正规文法,此题有穷自动机对应的正规文法GS 为：A aB|bB|cC B aB|bD|aE|cC|b|a C bB|cC|cE|c D bD|bE aE|abb4a2abstart1cbc53ac图 1 有穷自动机的状态转换图2. 给定如图2 所示的有穷自动机,试用正规表达式给出它能接受的语言集合.bbaba012b3aa

2、图 2 有穷自动机解：此题考查正规表达式与有穷自动机的等价性.对于一个在输入字母表上的FAM,肯定可以在字母表上构造一个正规表达式e,使得 Le=LM.依据状态转换图,从开头状态动身,可以有任意个 （包括 0 个）b 作为句子的开头部分.从 0 状态动身,每输入一个a,不许输入两个b 才能到达终止状态后,仍可以通过输入a 回到状态 1,或输入b 回到状态0,然后进入递归过程,再输入相同的符号串,所以,该有穷自动机描述的语言为：可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 1 页,共 5 页 - - - - - - - - - -可

3、编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点b*aa*b*b*3. 构造下述正规表达式的DFA . Xy*|yx*y|xyx解：此题考查由正规表达式构造有穷自动机的方法,此题可依据由正规表达式构造等价的NFA ,NFA 确定化, DFA 最小化 3 步进行求解.（ 1）依据题中所给的正规表达式得到相应的DFA 如图 3 所示.yABxxySCDEyZxxFyG图 3 正规表达式Xy*|yx*y|xyx的 DFA .（ 2）依据该 NFA 采纳子集法构造确定DFA 其过程如表1（ 已换名）所示.表 1将

4、 NFA 确定化为 DFA 的过程SI0A, B, F, ZIx1C, D, EIy2A, B, F, Z1B, G, Z3C, D, E2D, E4Z5B, G , Z3Z5B, Z6D, E4D, E4Z5Z5B, Z6B, Z6以全部包含NFA 的终止状态Z 的 DFA 状态作为终止状态,得到DFA 相应的状态转换图如 图 4 所示可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 2 页,共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - -

5、- - - - - - - -名师整理精华学问点y3y16xxxy0x4yy2y55图 4DFA 的状态转换图（ 3）对 DFA 进行最小化,过程如下：已知 K=0,1,2,3,4,5,6 .第一将K 分成两个子集K 1=0,2,3（非终态集）K 2=1,3,4,6（终态集）在状态集合K1=0,2,3 中,由于0 x =1 . K 22,4 x =4 . K 1所以状态0 与状态 2 , 4 不等价,故K1 可分割为K 11=0K12=2,4在状态集合K12=2 , 4 中,由于有2 , 4 x=42,4 y=5 . K 2所以,状态2 和状态 4 等价.在状态集合K 2=1,3,4,6 中,

6、状态5 无输入,状态3 有 x 、y 输入,状态1 与状态 6 只有 y 输入,所以可将K 2 分割为K 21=1,6K 22=3K 23=5在状态集合K 21=1 ,6 中,状态 1 输入 y 到达状态3,状态 6 输入 y 到达状态6,所以状态 1 与 6 也不等价.进一步将K 21 分割为K 211=1K 212=6于是,将原状态集合划分为：0 、2 , 4 、1 、3 、 5 、6 .选2 ,4 中的 2 作为代表,原先由状态4 导入（出）其余状态的弧改为有状态2 导入（出）.然后消去状态4.最终得到最小化后的状态转化图如图5 所示.可编辑资料 - - - 欢迎下载精品_精品资料_学习

7、资料 名师精选 - - - - - - - - - -第 3 页,共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点y3y16xy0xxy2y55图 5 正规表达式Xy*|yx*y|xyx的最小化DFA4. 构造正规表达式（011） *00 相应的 DFA .解：此题考查由正规表达式构造确定的有穷自动机的方法.（ 1）构造正规表达式（011） *00 的 DFA .依据图 3.2 所示的转换规章构造正规表达式（011） *00 对应的 NFA 如图 6 所

8、示.可编辑资料 - - - 欢迎下载精品_精品资料_0SAB0C0Z可编辑资料 - - - 欢迎下载精品_精品资料_1图 6 正规表达式（ 011） *00 的 DFA（ 2）由正规表达式（011）*00 的 NFA 构造确定的有穷自动机DFA .以 NFA 的开头状态S 的 闭包 -CLOSUR（E S ）作为 DFA的开头状态,采纳子集法将图 3.43 中所式的NFA确定化,其过程如表2 所示.S,A, BI表20A, B, C将NFAIx确定化为1DFA 的过程A, BIy2A, B, C1A, B, C, Z3A, B2A, B2A, B, C1A, B2A, B, C, Z3A, B

9、, C, Z3A, B2以全部包含NFA的终止状态Z 的 DFA状态作为终止状态,得到 DFA相应的状态转换图（以换名）如图7 所示.可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 4 页,共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点100001031121图 7正规表达式（ 0|1） *00 的 DFA（ 3）对该 DFA进行最小化.采纳够造状态集划分的方法对DFA进行最小化,过程如下： 以知 K=0 , 1,2, 3 .第一将K 分成两个子集K 1=0,1,2（非终态集）K 2=3（终态集）在 K1=0,1,2中,有00=1 K 110=3 K 220 =1 K 101=2 K 111=2 K 121=2 K 1可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 5 页,共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载