词法分析习题.doc
《词法分析习题.doc》由会员分享,可在线阅读,更多相关《词法分析习题.doc(5页珍藏版)》请在三一文库上搜索。
1、词法分析补充习题1. 构造与正规式(a|ba)*等价的状态最少的DFA。2. 构造与正规式(a|b)*a(a|b)等价的状态最少的DFA。3. 构造与正规式(a|b)* aa等价的状态最少的DFA。1. 解答:(1)构造NFA如图1所示:aZASbaB图1(aba)*的NFA(2)NFA确定化为DFA的过程如下表所示:IIaIbS, A, ZA, ZBA, ZA, ZBBA, Z 为重新标注的状态号。画出相应的状态图如图2所示。a2aba1b3图2(aba)*的DFA(3)DFA最小化首先得到两个子集K1 = 3 和 K2 = 1,2。考察K2,由于1,2a = 2 K2,1,2b = 3 K
2、1,所以K2不可再分。用1来代表K2并删除3,得到最小化DFA的状态图,图3所示.b31aa图3 正规式(ab a)*的最小化DFA2. 解答(1)构造NFA,见图1 aaZCaBSAbb图1 正规式(a|b)*a (a|b)的NFA(2)NFA确定化为DFA的过程表和相应DFA的状态图,见图2 IIaIbS, A, BA, B, CA, BA, B, CA, B, C, ZA, B, ZA, BA, B, CA, BA, B, C, ZA, B, C, ZA, B, ZA, B, ZA, B, C A, B 为重新标注的状态号。画出相应的状态图如图2所示。a4a2aa1bab5bb3b图2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 词法 分析 习题
链接地址:https://www.31doc.com/p-5707926.html