第7部分习题答案
更新时间:2023-12-10 11:12:01 阅读量: 教育文库 文档下载
- fifa主线任务第7部分推荐度:
- 相关推荐
1.15.若L是正规语言,证明下面
11L语言也是正规语言。L语言的定义是 221L = {x | ?y. xy ? L & |x| = |y| } 2答案 因为L是正规语言,那么存在一个DFA M = (S, ?, ?, s, F),它接受语言L。接受语言的DFA M? = (S?, ?, ??, s?, F?)可如下构造。 1.S?的每个状态是一个二元组?s1, S1?,其中s1?S,S1 ? S。 2.?? (?s1, S1?, a) = ?s2, S2?,其中
s2 = ? (s1, a) S2 = { s2 | ? s1? S1??b???? (s2, b) = s1} 3.s? = ?s, F?
4.F? = {?s1, S1? | s1 ? S1}
1L2可以证明这是接受语言
11L的DFA,因此L是正规语言(证明比较复杂,我们在此略去)。 22分析 这个题目超出的编译课程的范围。但是如果理解了这儿的解答,那就掌握了证明正规
语言的一种很重要的技巧。下面我们说明,为什么这样定义DFA M?。 长度为n的串w,若它是语言L的某个句子的前缀,那么从M的开始状态s,经n步转换,到达某个状态sn。该串是否属于
1L,取决于是否存在从sn开始到某个接受状态的路径,2其长度为n。
怎样判断是否存在这样的到某个接受状态的路径呢?我们可以在M的状态转换图上按下面的步骤办。
1.首先找出从任意接受状态逆向任意走一步能到达的所有状态,把这个状态集合称做R1。
2.再找出从R1的任意状态逆向任意走一步能到达的所有状态,把这个状态集合称做R2。
3.这样逆向操作n步后,得到状态集合Rn。
4.若sn在Rn中,那么串w属于
1L,否则不是。 2 可以看出,上面定义的M?是在M上同时跟踪从开始状态出发的正向状态转换和从接受状态集合出发的逆向搜索所有状态。我们再看一下M?的定义。 1.S?的每个状态之所以是一个二元组?s1, S1?,是因为需要用s1来表示正向的状态转换,用S1来表示逆向搜索。 2.再看状态转换的定义?? (?s1, S1?, a) = ?s2, S2?,其中s2 = ? (s1, a)表示了M上正向一步转换到达的状态,S2 = { s2 | ? s1? S1??b???? (s2, b) = s1}表示了M上逆向一步搜索到达的状态集合。 3.开始状态s? = ?s, F?表示在M上的跟踪是从开始状态和接受状态集合这两端启动。 4.接受状态F? = {?s1, S1? | s1 ? S1}表达的意思是,若在M上从开始状态经n转换到s1,那么一定存在长度为n的从s1到某个接受状态的路径。
下面我们以1.4题的正规语言为例。不难理解,该语言的
1语言应该是字母表?={0, 1}2 1
上的所有串。我们用上面的方法来构造接受它的DFA。该DFA的开始状态s0 = ?0, {0}?。 状态s0: ?0, {0}? ? (s0, 0) = ?2, {1, 2}? ? (s0, 1) = ?1, {1, 2}? 状态s1: ?2, {1, 2}? ? (s1, 0) = ?0, {0, 3}? ? (s1, 1) = ?3, {0, 3}? 状态s2: ?1, {1, 2}? ? (s2, 0) = ?3, {0, 3}? ? (s2, 1) = ?0, {0, 3}? 状态s3: ?0, {0, 3}? ? (s3, 0) = ?2, {1, 2}? ? (s3, 1) = ?1, {1, 2}? 状态s4: ?3, {0, 3}? ? (s4, 0) = ?1, {1, 2}? ? (s4, 1) = ?2, {1, 2}?
从s0到s4的这五个状态,每个状态的第一元都在第二元的集合中,因此这五个状态都是接受状态。这个DFA的图形表示见图1.17(图中用状态0, 1, 2, 3和4代替了这里对应的状态)。显然,它能接受字母表?={0, 1}上所有的串,化简这个DFA可以得到只有一个状态的DFA。
start 0 1 1 0 0 0 1 3 1 图1.17 接受?={0, 1}上所有串的一个DFA
1.16 保留字、关键字和标准标识符之间的区别是什么?
答案 保留字是语言预先确定了含义的单词,程序员不可以对这样的单词重新声明它的含义。如PASCAL语言的type 和procedure等。词法分析器读到一个符合标识符拼写的单词时,都要和保留字进行比较,以确定该单词是标识符呢还是哪个保留字。 很多语言的关键字是保留的,因此和上面的保留字没有区别,如C语言和Java语言。但是FORTRAN语言的关键字不保留,如IF,当它作为语句的第一个单词时,很可能是关键字,但也不排除是用户定义的标识符。这给词法分析带来很大困难,因为识别单词和该单词所处的上下文有关。现在的语言都不会象FORTRAN这样来定义关键字。 标准标识符是预先确定了含义的单词,但是程序员可以重新声明它的含义。在这个声明的作用域内,程序员声明的含义起作用,而预先确定的含义消失,如PASCAL语言的integer和true等。词法分析器对标准标识符没有什么特别的处理,由符号表管理来解决这件事。
1.17 词法分析器能查出源程序中什么样的错误,举例说明。
答案 词法分析器对源程序采取非常局部的观点,因此象C语言的语句 fi (a == f (x) ) …
中,词法分析器把fi当作一个普通的标识符交给编译的后续阶段,而不会把它看成是关键字if的拼写错。 PASCAL语言要求作为实型常量的小数点后面必须有数字,如果程序中出现小数点后面没有数字情况,它由词法分析器报错。
1.18 一个C语言编译器编译下面的函数时,报告parse error before ‘else’。这是因为else的前面少了一个分号。但是如果第一个注释 /* then part */ 误写成
2
1 0 4 0 1 2 /* then part
那么该编译器发现不了遗漏分号的错误。这是为什么?
long gcd(p,q) long p,q; { if (p%q == 0) /* then part */ return q else /* else part */ return gcd(q, p%q);
}
答案 此时编译器认为
/* then part
return q else /* else part */
是程序的注释,因此它不可能再发现else 前面的语法错误。
分析 这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的,而词法分析器对程序采取非常局部的观点。当进入第一个注释后,词法分析器忽略输入符号,一直到出现注释的右括号为止,由于第一个注释缺少右括号,所以词法分析器在读到第二个注释的右括号时,才认为第一个注释处理结束。 为克服这个问题,后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释始于双连字符(--),随行的结束而终止。如果用Ada语言的注释格式,那么上面函数应写成
long gcd(p,q) long p,q; { if (p%q == 0) -- then part return q else -- else part return gcd(q, p%q);
}
3
正在阅读:
第7部分习题答案12-10
结合当前国际局势,阐述新时代中国外交政策06-02
2013年职业经理人资格证考试题及答案每日一讲(9月7日)10-31
咨询技能文档04-17
慈溪城市地下空间开发利用及人防建设专项规划 - 图文12-10
一堵墙11-03
专题3 牛顿运动定律10-30
家庭教育理论学习心得03-27
8B Unit3 exercise111-24
德育工作先进个人事迹03-03
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 习题
- 答案
- 部分
- MAPGIS二次开发讲义
- 广州市建筑工程结构实体质量监督抽测办法穗建质303号
- 初中数学全国优质课评比获奖说课稿大集合
- 关于中国城市轨道交通机电设备国产化政策和实施原则
- 非谓语动词 句子分析
- 教学目标的分类
- 《金属学及热处理》复习习题及答案
- 以生命捍卫淮南人民的胜利果实
- 船舶推进概念
- 煤矿皮带机保护装置安装位置-技术标准
- 2016年PH计现状研究及发展趋势
- 给带点字选择正确的读音
- 浅谈冷冻法在地铁联络通道施工中的应用
- 《新老师应如何避免教学活动时间的隐性浪费》
- 《SQL数据库管理与开发》试题(F卷)
- 印发河源市2010年政府集中采购目录及政府采购限额标准的通知
- 青年岗位能手事迹材料
- 初中语文“经典诵读与海量阅读”校本课程实施方案
- 2019-2020年中考语文试题分类汇编:文学常识与名著专题
- 北京协和医学院博士研究生指导教师名单(2012)