没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全第三章词法分析-答案解析 1

第三章词法分析-答案解析 1

需积分: 0 0 下载量 15 浏览量 2022-08-08 23:07:02 上传评论收藏 768KB DOCX 举报

温馨提示

试读

19页

引入初始状态X和Y：得到的NFA是对NFA确定化的转换矩阵为：确定化以后的DFA为最小化DFA的过程：非终态集合I(1)={0，1，2，3，4，5，8，10，1

资源详情

资源评论

资源推荐

第三章词法分析作业

专业班级：学生姓名：学生学号：

3.1 给定文法 G[S]：

S→aA|bQ

A→aA|bB|b

B→bD|aQ

Q→aQ|bD|b

D→bB|aA

E→aB|bF

F→bD|aE|b

请构造相应最小化的 DFA。

答：设初始状态为 S，终态为 T，则状态转换矩阵为

状态结点

{A}

{Q}

{A}

{B,T}

{Q}

{D}

{Q}

{D,T}

{A}

{B}

{F}

{E}

{D,T}

状态转换矩阵生成的 NFA 为：

设确定后的 DFA 的终态为 Z，则 NFA 的确定化过程矩阵：

{S}

{A}

{Q}

{A}

{B,Z}

{Q}

{D,Z}

{B,Z}

{Q}

{D}

{D,Z}

{A}

{B}

{D}

{A}

{B}

{Q}

{D}

确定的 DFA 的状态转换图为

将此 DFA 化简后如下：

对 DFA 的最小化的过程：

1. 非终态集合 I(1) = {0,1,2,5,6}, 终态集合 I(2) = {3,4}

2. 考察非终态集合 I(1) ={0,1,2,5,6}，查 NFA 的确定化过程矩阵

I(1)a = {1, 2} I(1)b = {2,3,4,5,6}，I(1)b 中的状态分属 I(1)和 I(2)，因此可分，

其中{0,5,6}b 属于 I(1), {1,2}属于 I(2)，所以分为{0,5,6}, {1,2};

目前状态集合 I(11) = {0,5,6}, I(12) = {1,2}, I(2) = {3,4}

3. 考察 I(11) = {0, 5, 6}，查 NFA 的确定化过程矩阵

I(11)a = {1, 2}，I(11)b = {2, 5, 6}，I(11)b 中的状态分属 I(11)和 I(12)，因此可

分，其中{0}b 属于 I(12), {5,6}b 属于 I(11)，所以分为{0}, {5,6};

目前状态集合 I(111) = {0}, I(112) = {5,6}, I(12) = {1,2}, I(2) = {3,4}

4. 考察 I(112) = {5,6}，查 NFA 的确定化过程矩阵，I(112)a 和 I(112)b 都在同一

个子集，因此不可分；

5. 考察 I(12) = {1,2}，查 NFA 的确定化过程矩阵，I(12)a 和 I(12)b 都在同一个

子集，因此不可分；

6. 考察 I(2) = {3,4}，查 NFA 的确定化过程矩阵，I(2)a 和 I(2)b 都在同一个子集，

因此不可分；

7. 最终状态集合为{0}, {5,6}, {1,2}, {3,4}，标记为 T

, T

。

最小化的状态转换矩阵：终态结点为红字加粗

{0}

{1,2}

{3,4}

{5,6}

3.2 构造下列正规式相应的最小化的 DFA

1(0∣1)*101

1(1010*∣1(010)*1)*0

0*10*10*10*

(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*

答：

（1）1(0∣1)*101

首先构造 NFA；引入初始状态 X 和 Y：

对 NFA 确定化过程矩阵：

NFA 状态

{X}

{1，2，3}

{2，3}

{2，3，4}

{2，3}

{2，3，4}

{2，3，5}

{2，3，4}

{2，3，5}

{2，3}

{2，3，4，Y}

{2，3，5}

{2，3，4}

确定化后的 DFA 是：

对 DFA 的最小化的过程：

1. 非终态集合 I(1) = {0,1,2,3,4}, 终态集合 I(2) = {5}

1(0|1)*101

剩余18页未读，继续阅读

内容反馈

八位数花园

粉丝: 44
资源: 281

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

第三章词法分析-答案解析 1

评论0

最新资源

第三章 词法分析-答案解析 1

评论0

编译原理第3章 词法分析.pdf

词法分析 - 测试文档1

编译原理 陈火旺（第三版）第三章 词法分析.ppt

词法分析-scanner

编译原理 词法分析-语法分析-语义分析

第三章 词法分析1

第三章 词法分析1

编译原理 词法分析解析

antlr指南第三章词法分析

编译原理第三章：词法分析

词法分析-语法分析 实验课程序

编译原理第三章课件—词法分析

learning-lex-yacc：学习词法分析和解析

[高等教育]第三章词法分析.pdf

第三章_词法分析(修改版)_(编译原理)

软件编译原理：第三章 词法分析.pdf

flex-bison:flex＆bison（词法分析和解析）

C++-代码解析(词法分析、语法分析) (2).docx

C++-代码解析(词法分析、语法分析).docx

C++-代码解析(词法分析、语法分析).pdf

C++-代码解析(词法分析、语法分析) (2).pdf

编译 原理 第二章 词法 分析 课后 答案

C++ 代码解析(词法分析、语法分析).pdf

C++ 代码解析(词法分析、语法分析).docx

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

最新资源

第三章词法分析-答案解析 1

编译原理第3章词法分析.pdf

编译原理陈火旺（第三版）第三章词法分析.ppt

编译原理词法分析-语法分析-语义分析

第三章词法分析1

第三章词法分析1

编译原理词法分析解析

词法分析-语法分析实验课程序

软件编译原理：第三章词法分析.pdf

编译原理第二章词法分析课后答案