当前位置：文档之家 › 画出下列有限自动机的状态转换图

画出下列有限自动机的状态转换图

  • 格式：doc
  • 大小：178.50 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

第三章有穷自动机

第三章有穷自动机

例：将图示的DFA M最小化。
a
b
6
4
a
a
a
b
a
1
ab
5a
7
b3
b
b
2 b
1、将M状态分为两个子集： P0=({1,2,3,4},{5,6,7})
2、{1,2,3,4}读入a后划为： P1=({1,2},{3,4},{5,6,7})
3、进一步划分： P2=({1,2},{3},{4},{5,6,7})
对M的状态集S进行划分的步骤：
①把S的终态与非终态分开，分成两个子集， 形成基本划分，属于这两个不同子集的 状态是可区别的。
②假定某个时候已含m个子集，记={I(1) , I(2) , …,I(m) }且属于不同子集的状态是可 区别的，再检查中的每个I能否进一步划 分，对于某个I(i) ，令I(i) ={S1,S2,…,Sk}， 若存在一个输入字符使得move(I(i) ,a)不包 含在现行的某一子集I(i)中，则将I(i)一分 为二。
若M的某些结既是初态结，又是终态结，
或者存在一条从某个初态结到某个终态结 的道路，则空字可为M所接受。
例： NFA M=({0,1,2,3,4},{a,b},f,{0},{2,4})
f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1}
f(3,a)={4} f(1,b)={2} f(4,a)={4}
M’=(K, ,f,S,Z)
一个含有m个状态和n个输入字符的NFA 可表示为一张状态转换图，该图含有m个 状态结，每个结可射出若干条 箭弧与别的 结点相连接，每条弧用*中的一个字（不 一定要不同的字，且可以为空字）作标记 （称输入字），整个图至少含有一个初态 结以及若干个终态结。

2017年11月软件设计师上午真题及答案

2017年11月软件设计师上午真题及答案

2017年11月软件设计师上午真题1.在程序执行过程中，Cache与主存的地址映射是由（）完成的。

A.操作系统B.程序员调度C.硬件自动D.用户软件2.某四级指令流水线分别完成取指、取数、运算、保存结果四步操作。

若完成上述操作的时间依次为8ns、9ns、4ns、8ns，则该流水线的操作周期应至少为（）ns。

A.4B.8C.9D.333.内存按字节编址。

若用存储容量为32Kx8bit的存储器芯片构成地址从AOOOOH到DFFFFH的内存，则至少需要（）片芯片。

A.4B.8C.16D.324.计算机系统的主存主要是由（）构成的。

A.DRAMB.SRAMD.EEPROM5.以下关于海明码的叙述中，正确的是（）。

A.海明码利用奇偶性进行检错和纠错B.海明码的码距为1C.海明码可以检错但不能纠错D.海明码中数据位的长度与校验位的长度必须相同6.计算机运行过程中，CPU需要与外设进行数据交换。

采用（）控制技术时，CPU与外设可并行工作。

A.程序查询方式和中断方式B.中断方式和DMA方式C.程序查询方式和DMA方式D.程序查询方式、中断方式和DMA方式7.与HTTP相比，HTTPS协议对传输的内容进行加密，更加安全。

HTTPS 基于（）安全协议，其默认端口是（）。

A.RSAB.DESC.SSLD.SSHA.1023B.443C.809.下列攻击行为中，属于典型被动攻击的是（）。

A.拒绝服务攻击B.会话拦截C.系统干涉D.修改数据命令10.（）不属于入侵检测技术。

A.专家系统B.模型检测C.简单匹配D.漏洞扫描11.以下关于防火墙功能特性的叙述中，不正确的是（）。

A.控制进出网络的数据包和数据流向B.提供流量信息的日志和审计C.隐藏内部IP以及网络结构细节D.提供漏洞扫描功能12.某软件公司项目组的程序员在程序编写完成后均按公司规定撰写文档，并上交公司存档。

此情形下，该软件文档著作权应由（）享有。

A.程序员B.公司与项目组共同C.公司D.项目组全体人员13.我国商标法规定了申请注册的商标不得使用的文字和图形，其中包括县级以上行政区的地名（文字）。

编译原理之有限自动机

编译原理之有限自动机

b
4
5
2.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8}
状态 A
输入符号 ab B
a
2
3
开始
0
1
a
b
6
7
8
9
b
4
5
2.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8}
识别器：是一个程序，取串x作为输入，当 x是语言的句子时，它回答“是”，否则回 答“不是”。 状态转换图（有限自动机）识别器 确定/不确定有限自动机——时空权衡问题
确定有限自动机：快，空间大
2.3 有 限 自 动 机
2.3.1 不确定的有限自动机（简称NFA）
一个数学模型，它包括: 状态集合S；
缺点：1、输入字 符包括
NFA能到达的所有状态：s1, s2, …, sk，则 DFA到达状态{s1, s2, …, sk}
2.3 有 限 自 动 机
输入符号
状态 a
b
a
2
3
开始
0
1
a
b
6
7
8
9
b
4
5
2.3 有 限 自 动 机
A = {0, 1, 2, 4, 7}
状态 A
输入符号 ab
a
2
3
开始
0
1
a
b
6
7
8
9
输入符号 ab BC BD
a
2
3
开始
2.2 词法记号的描述与识别

编译原理 3.2正规文法和状态转换图

编译原理 3.2正规文法和状态转换图

2020/6/18
第30页/共24页
一个简单的词法分析器示例
1 C语言子集的单词符号表示 2 C语言子集对应的状态转换图的设计 3 状态转换图的实现
2020/6/18
第31页/共24页
1 C语言子集的单词符号表示
大多数程序语言的单词符号都可用 状态转换图予以识别。下面构造一个C 语言子集的简单词法分析器，该C语言 子集的所有单词符号及其种别编码和内 码值如下表所示。
开始符号S作为初始状态； S 设一符号F不属于V作为终止状态； F
2020/6/18
第7页/共24页
形如A→aB的规则：从结点A引一条矢线到结
点B，并用符号a标记这条矢线；
a
A
B
形如A→a的规则：从结点A引一条矢线到终态
结点F，并用符号a标记这条矢线；
a
A
F
2020/6/18
第8页/共24页
则有：S=> a1A1=> a1 a2A2=> a1 a2 a3A3=> … => a1 a2 a3 … an-1An-1=> a1a2a3…an
事实上，在利用状态转换图M对符号串ω进行识别的 过程中，M中的每一次状态转换都模拟了G中的一步 直接推导，所以，上述方法是一个自顶向下的分析
方法。
2020/6/18
a
R
A
2020/6/18
第16页/共24页
例如：G[Z]：Z→U0∣V1 U →Z1∣1 V →Z0∣0
1
2020/6/18
1
U
初态 R
0
V
0
Z
1
0
第17页/共24页
二、状态图的使用——识别句子

编译原理 第3章习题解答

编译原理 第3章习题解答

第三章习题参考解答3.1 构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。

⑥它能识别形式如±dd*⋅ d*E ±dd的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

3.2 构造下列正规表达式的DFSA：① xy*∣yx*y∣xyx；② 00∣(01)*∣11；③ 01((10∣01)*(11∣00))*01；④ a(ab*∣ba*)*b。

3.3 消除图3.24所示自动机的空移。

bεq1q2q3aba,bqaq6q4q5abεεε图3.24 含空移的自动机3.4 将图3.25所示NDFSA确定化和最小化。

xyqq1q2q4q3xyxyx,yx图3.25 待确定化的NDFSA3.5 设e、e1、e2是字母表∑上的正规表达式，试证明① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1};⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。

3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]:Z→A0A→A0∣Z1∣03.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=∅, f(y, b)={x, y}。

试对此NDFSA确定化。

3.8 设文法G[〈单词〉]：〈单词〉→〈标识符〉∣〈无符号整数〉〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉〈字母〉→a∣b〈数字〉→1∣2试写出相应的有限自动机和状态图。

编译原理1-3章作业

编译原理1-3章作业

（b）已是DFA，只需最少化
b
=> 0
b 2
3
b
a
a
8、令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|I
(1)给出i+i*i、i*(i+i)的最左推导和最右推导； (2)给出i+i+i、 i+i*i和i-i-i的语法树。
9、证明下面的文法是二义性的： S->iSeS|iS|i
证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示， 因此该文法是二义的。
第三章
7、构造下列正规式相应的DFA 1(0|1)*101 0*10*10*10* 9、对下面情况给出DFA及正规表达式 （1）{0,1}上的含有子串010的所有串； 12、将图3.18的(a)和(b)分别确定化和最少化。
1(0|1)*101 (1) 构造NFA：
(2) 确定化
构造状态转换矩阵如下：
8、令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|I
(1)给出i+i*i、i*(i+i)的最左推导和最右推导； (2)给出i+i+i、 i+i*i和i-i-i的语法树。 答：(1) 最左推导： E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F) =>i*(i+i) 最右推导： E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i) =>F*(i+i)=>i*(i+i)

软件设计师上午基础知识考试选择题专项强化真题试卷9(题后含答案及解析)

软件设计师上午基础知识考试选择题专项强化真题试卷9(题后含答案及解析)

软件设计师上午基础知识考试选择题专项强化真题试卷9(题后含答案及解析)题型有：1.1．某确定性有限自动机(DFA)的状态转换图如下图所示，令d=0｜1｜2｜…｜9，则以下字符串中，能被该DFA接受的是(49)。

A．3857B．120000C．-123.67D．5760000000正确答案：C解析：本题程序语言翻译基础知识。

翻译高级语言源程序的第一步工作是进行词法分析，即将源程序中的单词(记号)识别出来，该过程可用有限自动机描述。

自动机M识别一个字符串的过程是从开始状态出发，根据字符串中的字符依次进行状态转移，若能到达终态且字符串结束，则该字符串可被自动机M识别。

考查题目中的选项，3857的识别过程是状态0→状态1→状态1→状态1，状态1不是终态；字符串 1.2E+5中的“+”不能识别；字符串0.576E10的识别过程是状态0→状态1→状态5→状态6→状态6，在状态6下不能识别E。

字符串-123.67的识别过程是状态0→状态4→状态1→状态1→状态5→状态6→状态6，因此该字符串可被题中的自动机识别。

2．一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有(62)特性。

A．有穷性B．可行性C．确定性D．健壮性正确答案：B解析：本题考查算法基本概念。

一个算法是对某类给定问题求解过程的精确描述，算法有5个基本特性：有穷性、确定性、可行性、有输入和输出。

其中，有穷性是指对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成。

确定性是指对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。

可行性是指算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

题目中的描述说明的是算法的可行性。

正规式与有限自动机

正规式与有限自动机

正规式与有限自动机正规式与有限自动机之间的转换1）有限自动机转换为正规式对于S上的NFAA/,可以构造一个S上的正规式/?,使得切⑷。

拓广状态转换图的概念，令每条弧可用一个正规式作标记。

为S上的NFA Af构造相应的正规式及，分为如下两步。

（1）在M的状态转换图中加两个节点，一个x节点，一个y节点。

从x节点到NFAM 的初始状态节点引一条弧并用e标记，从NFAM的所有终态节点到y节点引一条弧并用e 标记。

形成一个与A/等价的MS AT只有一个初态jc和一个终态少。

（2）按下面的方法逐步消去中除x和；；的所有节点。

在消除节点的过程中，用正规式来标记弧，最后节点jc和；；之间弧上的标记就是所求的正规式。

消除节点的规则如图2-12所示。

2）正规式转换为有限自动机同样地，对于S上的每个正规式/?,可以构造一个S上的NFAAf,使得L（A0=Z（及）。

（1）对于正规式i,可用图>13所示的拓广状态图表示。

R o（1）通过对正规式/?进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是E上的一个字符或e,转换规则如图2-14所示。

最后所得的图即为一个NFAM,JC为初态节点，少为终态节点。

显然，L（A0=I（及）。

【试题2-24】2011年11月真题48下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式（48）表示。

A. (0|1)*01B. 1*0*10*1C. 1*(0)*01D. 1*(0|10)*1*分析：在正规式中，符号*表示重复若干次（包括0次），符号|表示“或”。

在状态A，可以输入1或0，如果输入1还可以回到状态A，如果输入0直接到达状态B；在状态B，可以输入0或1，如果输入0则还回到状态B，而输入1，则进入到状态C；在状态C可以输入0或1，输入0到达状态B，输入1到达状态A，但由于C是终态，自动机可识别的语言是由0、1构成的字符串的集合，但该集合必须以01结果，因此选项A正确。

编译原理课后习题答案

编译原理课后习题答案

第一章1．解答：程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。

一般可以划分为低级语言和高级语言两大类。

低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。

高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如FORTRAN、Pascal、C等等我们熟悉的语言是高级语言。

语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。

它一般可分为解释程序和翻译程序两大类。

翻译程序：翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另一种语言书写的程序（称为目标程序）。

若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。

若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。

解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。

2．解答：编译程序的总框图见图1.2。

其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号。

语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。

优化器对中间代码进行优化处理。

一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。

编译原理 3.3有限自动机

编译原理 3.3有限自动机
且定义 f（ {Sk1，Sk2，…，Skm}，w）= U f（Ski，w） i 1
则有 f（S，aw）= f（ f （S，a），w ）
m
=
U
i 1
f（Ski，w）
2020/6/18
第13页/共42页
讨论问题3：
NFA M所能识别的语言：对于Σ*中的符号串x，
若集合 f（S0，x）中含有属于终态集Z中的状态 （即 至少存在一条从S0到某一终态的通路，把此通路中所 有矢线上的标记连接起来就是符号串x），我们就说x 为M所接受，所有这样的x所组成的集合称为NFA M 的接受集，记作 L（M）。
f’(q0,a) =q0 f’(q0,b) =q1
{q0, q1 , q2}
第二步
2020/6/18
{q0, q1 , q2}
对于c，T=f(q0,c)= f({S0, S1, S2,S3},ca) ，
ε_closure(T) = ε_closure({S2})= {S2,
S3} = q2
S0 ε
f’(bq0,c) =q2
且{R1,R2,…,Rj}∩Z≠Ø}
2020/6/18
第21页/共42页
例：NFA M =({S0,S1}，{a，b}，f，S0，{S1} )
a
b
a,b
S0
S1
b
a
b
S0 {S0,S1} {S1}
S1
Ø
{S0,S1}
DFA M ′ =(K′，{a，b}，,f ′, S0 ′, Z′)
2020/6/18
第9页/共42页
正规文法 L（G）
必定存在 反之亦然
DFA M
=
L（M）
2020/6/18

习题参考答案-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

习题参考答案-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

附录部分习题参考答案第1章习题1. 解释下列术语。

翻译程序，编译程序，解释程序，源程序，目标程序，遍，前端，后端解答：略！2. 高级语言程序有哪两种执行方式?阐述其主要异同点。

描述编译方式执行程序的过程。

解答：略！3. 在你所使用的C语言编译器中，观察程序1.1经过预处理、编译、汇编、链接四个过程生成的中间结果。

解答：略！4. 编译程序有哪些主要构成成分？各自的主要功能是什么？解答：略！5. 编译程序的构造需要掌握哪些原理和技术？编译程序构造工具的作用是什么？解答：略！6. 复习C语言，其字母表中有哪些符号？有哪些关键字、运算符和界符？标识符、整数和实数的构成规则是怎样的？各种语句和表达式的结构是什么样的？解答：略！7.编译技术可应用在哪些领域？解答：略！8. 你能解释在Java编译器中，输入某个符号后会提示一些单词、某些单词会变为不同的颜色是如何实现的吗？你能解释在Code Blocks中在输入{后，会自动添加}，输入do 会自动添加while()是为什么吗？解答：略！第2章习题1. 判断题，对下面的陈述，正确的在陈述后的括号内画√，否则画×。

(1) 有穷自动机识别的语言是正规语言。

（）(2) 若r1和r2是Σ上的正则表达式，则r1|r2也是。

（）(3) 设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。

（）(4) 令Σ＝{a,b}，则所有以b开头的字构成的正规集的正则表达式为b*(a|b)*。

（）(5) 对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。

（）1解答：略！2.从供选择的答案中，选出应填入下面叙述中？内的最确切的解答。

有穷自动机可用五元组（Q，V T，δ，q0，Q f）来描述，设有一有穷自动机M定义如下：V T={0,1}，Q={q0,q1,q2}，Q f={q2}，δ的定义为：δ (q0，0)=q1δ (q1，0)=q2δ (q2，1)=q2δ (q2，0)=q2M是一个 A 有穷状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。

第3章-2-状态转换图

第3章-2-状态转换图


例2：
字母
字母或数字
0
1
其它
②
*
PROCEDURE Pro0; BEGIN Getchar; IF char IN [‘A’..‘Z’ ] then pro1 else error; END; Procedure pro1; begin getchar; while char IN [‘A’..‘Z’, ‘o’..‘g’ ] DO begin concat; getchar; End; pro2; End; procedure pro2; begin retract; return(101,TOKEN ); end;
识别无符号数的状态矩阵
当前状 态 0 扫描字符 d . ther d . E other d E other d other d + other d other d other 语义处理操作或接受动作 {w=0;n=0;p=0;e=1;w=w*10+d} {w=0;n=0;p=0;e=1;} error {w=w*10+d;} {return ( ICON= w ); {n++; w=w*10+d;} {return (FCON =w*pow(10,e*p-n) ) ;} {n++;w=w*10+d;} error {p=p*10+d;} e=-1; error {p=p*10+d;} error {p=p*10+d;} {return (FCON=w*pow(10,e*p-n) ); 后继状 态 1 3 1 2 4 end 2 4 end 2 6 5 5 6 6 end
步骤 1 2 3 4 5 6
当前状态 余留的符号串 R U U U S S 00011 0011 011 11 1 (识别结束)

程序设计语言基础(答案)

程序设计语言基础(答案)

●已知文法G[S]:S→A0|Bl，A→S1|1，B→S0|0；该文法属于乔姆斯基定义的__(12)__文法，它不能产生串__(13)__。

(12) A. 0 型B. 1 型C. 2 型D. 3 型(13) A. 0011 B. 1010 C. 1001 D. 0101●语言L={ambn|m≥0，n≥1}的正规表达式是__(14)__。

(14) A. a*bb* B. aa*bb* C. aa*b* D. a*b*●一个文法G=(N，T，P，S)，其中N 是非终结符号的集合，T 是终结符号的集合，P 是产生式集合，S 是开始符号，令集合V=N∪T，那么G 所描述的语言是__(15)__ 的集合。

(15) A．由S 推导出的所有符号串B．由S 推导出的所有终结符号串C．V 中所有符号组成的符号串D．V 的闭包中的所有符号串●下图为一确定有限自动机的状态转换图，与该自动机等价的正规表达式是__（12）__，图中的__（13）__是可以合并的状态。

（12）A.(a|b)*bb(a*b*)* B.(a|b)*bba*|b*C.(a*b*)bb(a|b)*D.(a*|b*)*bb(a*|b*)（13）A.0 和1 B.2 和3 C.1 和2 D.0 和3正确答案：A解析：在状态转换图中，每一个结点代表一个状态，其中双圈是终结状态。

该题实际上是一个简化确定有限自动机(DFA)的过程，一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。

首先介绍2个概念：最小状态DFA和等价状态。

最小状态DFA必须满足以下2个条件。

(1)没有多余状态(死状态)：多余状态从该自动机的开始状态出发，任何输入串都不能到达的那个状态。

(2)没有2个状态是互相等价(不可区别)。

2个状态s和t如果同时满足下列2个条件，就称s和t是等价的。

(1)一致性：同是终态或同是非终态。

(2)蔓延性：从s出发读人某个a和从t出发读入某个a到达的状态等价。

编译原理复习

编译原理复习

1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。

2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。

3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。

4、编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个阶段，上述各阶段中还要进行表格处理和出错处理的工作。

5、编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码生成。

上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后阶段的输出是目标代码。

6、程序语言是由语法和语义两方面定义的。

语法指可以形成和产生一个合式的程序的一组规则，语义是定义一个程序的意义的一组规则。

7、一个名字的属性包括类型和作用域。

8、目标代码一般有三种形式：能够立即执行的机器语言代码，待装配的机器语言模块和汇编语言代码。

9、2型文法又称为（上下文无关文法），3型文法又为（正规文法）。

10、虽然名字都是用标识符表示的，但名字和标识符有着本质的区别。

11、词法分析器的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成单词符号串的中间程序。

12、执行词法分析的程序称为词法分析器或扫描器。

13、词法分析器所输出的单词符号常常表示成如下二元关系：（单词种别，单词自身值）。

14、词法分析器：是一种程序，它能将字符串形式的源程序改造成单词符号串形式的中间程序。

15、程序语言的单词符号包括：（标识符）、（运算符）、（常数）、（基本字）、界符等。

16、超前搜索：在词法分析过程中，有时为了确定词性，需要超前扫描若干个字符，这个动作为超前搜索。

17、状态转换图是一张有限方向图，其中结点代表状态，状态之间用箭弧连接，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类，状态中有一个初态，至少有一个终态。

18、自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一颗语法树。

编译原理(王力红著)习题答案 (2) (1)

编译原理(王力红著)习题答案 (2) (1)

习题11-1 说明解释程序和编译程序的区别。

答：通常，翻译程序可分为解释程序、汇编程序和编译程序。

所谓解释程序是一种将源程序按动态顺序逐句进行分析解释编译，边解释边执行、不产生目标程序的一种翻译程序。

这种翻译程序结构简单、占用内存较少，易于在执行过程中对源程序进行修改，但工作效率低，只适合一些规模较小的语言，如解释BASIC等。

而编译程序（也称编译器）是源语言为某种高级语言，目标语言为相应于某一计算机的汇编语言或机器语言的一种翻译程序。

这种编译程序将源程序翻译成执行时可完全独立于源程序的经优化的目标语言代码，因而运行效率高。

更为重要的是，它使工作于高级语言环境下的程序设计人员，不必考虑与机器有关的繁琐细节，却能完成机器语言所能完成的绝大多数工作。

在解释方式下，并不生成目标代码，而是直接执行源程序本身。

这是编译方式与解释方式的根本区别。

1-2 简述高级语言程序按编译方式的执行过程。

答：高级语言程序按编译方式的执行过程一般可分为两个阶段：编译阶段和运行阶段。

其中，编译阶段完成由源程序到目标程序的翻译，若目标程序是汇编语言程序，还需再通过汇编程序进一步翻译成机器语言程序。

而运行阶段的任务是在目标计算机上执行编译阶段所得到的目标程序。

但目标程序往往不能由计算机直接执行，一般还应有运行系统进行配合，这个运行系统包括链接程序和由这样一些子程序组成的系统库，如标准函数计算子程序、数组动态存储子程序等。

由链接程序将目标程序和系统库连接在一起，最终形成一个可执行程序，在计算机上直接执行。

1-3 什么是编译系统？答：通常将编译程序、链接程序、系统库、源程序编辑程序等软件组成的系统称为编译系统。

1-4 编译过程通常有哪几个阶段？简述各阶段的主要任务。

答：程序设计语言的编译过程一般可以分为词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成5个阶段。

词法分析是编译过程的第一个阶段。

该阶段的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位——单词，并指出其属性。

中级软件设计师2015上半年上午试题

中级软件设计师2015上半年上午试题

中级软件设计师2015上半年上午试题单项选择题1、机器字长为n位的二进制数可以用补码来表示（1)个不同的有符号定点小数。

A. 2nB. 2n-1C. 2n-1D. 2n-1+12、计算机中CPU对其访问速度最快的是（2)。

A. 内存B. CacheC. 通用寄存器D. 硬盘3、Cache的地址映像方式中，发生块冲突次数最小的是（3）。

A. 全相联映像B. 组相联映像C. 直接映像D. 无法确定4、计算机中CPU的中断响应时间指的是（4）的时间。

A. 从发出中的请求到中断处理结束B. 从中断处理开始到中断处理结束C. CPU分析判断中断请求D. 从发出中断请求到开始进入中断处理程序5、总线宽度为32bit，时钟频率为200MHz，若总线上每5个时钟周期传送一个32bit的字，则该总线的带宽为（5）MB/s。

A. 40B. 80C. 160D. 2006、以下关于指令流水线性能度量的叙述中，错误的是（6）。

A. 最大吞吐率取决于流水线中最慢一段所需的时间B. 如果流水线出现断流，加速比会明显下降C. 要使加速比和效率最大化应该对流水线各级采用相同的运行时间D. 流水线采用异步控制会明显提高其性能7、（7）协议在终端设备与远程站点之间建立安全连接。

A. ARPB. TelnetC. SSHD. WEP安全需求可划分为物理线路安全、网络安全、系统安全和应用安全。

下面的安全需求中属于系统安全的是（8），属于应用安全的是（9）。

8、A. 机房安全 B. 入侵检测 C. 漏洞补丁管理 D. 数据库安全9、A. 机房安全 B. 入侵检测 C. 漏洞补丁管理 D. 数据库安全10、王某是某公司的软件设计师，每当软件开发完成后均按公司规定编写软件文档，并提交公司存档。

那么该软件文档的著作权（10）享有。

A. 应由公司B. 应由公司和王某共同C. 应由王某D. 除署名权以外，著作权的其他权利由王某11、甲、乙两公司的软件设计师分别完成了相同的计算机程序发明，甲公司先于乙公司完成，乙公司先于甲公司使用。

画出下列有限自动机的状态转换图

画出下列有限自动机的状态转换图

习题33-1 画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？①M＝({S，A，B，C}，{0，1}，f，S，{S})，其转换函数为：f(S，0)=B f(B，0)= Sf(S，1)=A f(B，1)= Cf(A，0)=C f(C，0)= Af(A，1)=S f(C，1)= B参考答案：有限自动机的状态转换图它所识别或接受的语言是：L(M)={ε,00,11,0101,0110,1001,1010,0011,0000,1111,…,}由偶数个0或偶数个1组成的二进制串。

②M＝({0，1，2}，{a，b}解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)={a,aaa,abaa,ba,baaa,babaa,…}3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：①以aa为首的所有符号串集合；解答：正则式e=aa(a | b)*NFA：最小化：2习题来源：编译技术（王力红）习题解答：黎远松②以aa结尾的所有符号串集合；e=(a|b)*aa{X}为0{X,A}为1③含有相继两个a或相继两个b的所有符号串集合。

e=(a|b)*(aa|bb)(a|b)*3-3 试把下述NFA变换为DFA。

解答：最基本的方法是子集法：重命名：{0}为0，{1}为1，{1，2}为2，包含原终态2的{1，2}为新终态，于是所求DFA为：习题来源：编译技术（王力红）习题解答：黎远松解：最基本的方法：子集法：重命名：3-4 试把下列εFA变换为非εFA。

参考答案：习题来源：编译技术（王力红）习题解答：黎远松用子集法：3-5 试把下列FA确定化(若需要的话)和最小化。

参考答案：2,4状态是死状态，应删除。

只有一个状态的FA肯定是确定化的和最小化的。

习题来源：编译技术（王力红）习题解答：黎远松此FA是DFA，不需要确定化。

最小化：首先按终态与非终态划分：{0，1}，{2，3，4，5}；然后计算：对于输入a，b，{0，1}1等价。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

习题3
3-1 画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？
①M＝({S，A，B，C}，{0，1}，f，S，{S})，其转换函数为：
f(S，0)=B f(B，0)= S
f(S，1)=A f(B，1)= C
f(A，0)=C f(C，0)= A
f(A，1)=S f(C，1)= B
参考答案：有限自动机的状态转换图
它所识别或接受的语言是：
L(M)={ε,00,11,0101,0110,1001,1010,0011,0000,1111,…,}
由偶数个0或偶数个1组成的二进制串。

②M＝({0，1，2}，{a，b}
解答：有限自动机M的状态转换图：
有限自动机M所识别或接受的语言是：
L(M)={a,aaa,abaa,ba,baaa,babaa,…}
3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：①以aa为首的所有符号串集合；
解答：
正则式e=aa(a | b)*
NFA：
最小化：
2
②以aa结尾的所有符号串集合；
e=(a|b)*aa
{X}为0
{X,A}为1
③含有相继两个a或相继两个b的所有符号串集合。

e=(a|b)*(aa|bb)(a|b)*
3-3 试把下述NFA变换为DFA。

解答：
最基本的方法是子集法：
重命名：
{0}为0，{1}为1，{1，2}为2，包含原终态2的{1，2}为新终态，于是所求DFA为：
解：最基本的方法：子集法：
重命名：
3-4 试把下列εFA变换为非εFA。

参考答案：
用子集法：
3-5 试把下列FA确定化(若需要的话)和最小化。

参考答案：
2,4状态是死状态，应删除。

只有一个状态的FA肯定是确定化的和最小化的。

此FA是DFA，不需要确定化。

最小化：
首先按终态与非终态划分：{0，1}，{2，3，4，5}；然后计算：
对于输入a，b，{0，1}1等价。

对于输入a，{2，4}后继属于同一集合{0，1}，{3，5}后继属于同一集合{3，5}，故可继续划分为：{2，4}，{3，5}。

进一步计算：
3，5等价。

合并等价状态，最小化为：
3-6 构造下列正则表达式对应的确定有限自动机。

①a(b | a)*aba
②a(abab* | a(bab)*a)*b
3-7 写出下列FA所对应的正则表达式。

①在FA M的转换图上加进一个初态结X和一个终态结Y。

消去(0,1,b)这条弧：
e=(a(b+a)*)*
②消去(2,1,a)这条弧：e=ab(ab|ba|a)*
3-8 构造正则文法GLsl
·S‘mBI m
B?’mB nSlm
所对应的有限白动机。

3-9 给出下面的确定有限自动机所对应的正则文法。

3-11 用某种高级语言写出：
①非确定有限自动机确定化的算法；
②有限自动机简化的算法；
③把正则表达式转换为有限自动机的算法。

相关主题