第1次作业
更新时间:2024-06-26 15:35:01 阅读量: 综合文库 文档下载
第一次作业(如有疑问或发现有问题的答案,请联系lsj-5212@stu.xjtu.edu.cn,刘淞佳,西一A段410)
P35 习题2.1.1 图2-8中时一个滚大理石球玩具,在A或B处扔下一个大理石球。杠杆x1、x2和x3让大理石球落向左方或右方。每当一个大理石球遇到一个杠杆时,就引起这个杠杆在大理石球通过之后改变方向,所以下一个大理石球会走相反的分支。 a)用有穷自动机为这个玩具建模。设输入A和B表示扔进大理石球的入口。设接受对应于大理石球从D出来,不接受则表示大理石球从C出来。
A B b)非形式化地描述这个自动机的语言。
→000r 100r 011r
*000a 100r 011r 答案
001r a)状态用四位表示,
*001a 101r 000a 前三位用x1x2x3表示杠杆的方向,0向左,1向右,
010r 110r 001a 第四位用a和r表示,
*010a 110r 001a a表示前一个输入后结果为拒绝,
011r 111r 010a r表示前一个输入后结果为接受。
*011a 右边为转移表
100r 010r 111r
*100a 010r 111r b)这个语言是包含最后一个输出结果为D的所有投入A和B的 球
101r 011r 100a 的串。
*101a 011r 100a
P36 习题2.2.4 给出接受下列在字母表{0,1}上的语言的DFA:
A)所有以00结尾的串的集合。
B)所有带3个连续的0(不必在结尾)的串的集合。 C)带011字串的串的集合。
答案。
a)可以用转移图或者转移表。转移表如下所示。
→A B * C b)
→A B C * D c)
→A B C * D 0 B C D D 1 A A A D
0 B B B D 1 A C D D
0 B C C 1 A A A
110r *110a 111r *111a 000a 000a 001a 101a 101a 110a P36 习题2.2.10 考虑带下列转移表的DFA:
0 1 非形式化地描述这个DFA接受的语言,通过对输入串的长度
→A A B 进行归纳,证明这个描述是正确的。
* B B A 提示:当建立归纳假设时,断言什么样的输入导致每个状态,
而不只是断言什么样的输入导致接受状态,这样更明智些。 答案
这个自动机表示:状态A表示偶数个1,状态B表示奇数个1, 只有串有奇数个1的时候,串才会被接受。
当且仅当串w中有偶数个1时, (A,w) = A.。用归纳法证明如下 基础: |w| = 0。空串当然有偶数个 1 ,即0个 1,且 (A,w) = A. 归纳:假设对于比w 短的串命题成立。令 w = za, 其中 a 为 0 或1。
情形1: a = 0. 如果w有偶数个 1, 则z有偶数个1。由归纳假设, (A,z) = A。由转移表的DFA知 (A,w) = A.如果w有奇数个1, 则z有奇数个1. 由归纳假设, (A,z) = B, 由转移表的 DFA 知 (A,w) = B. 因此这种情况下 (A,w) = A 当且仅当 w 有偶数个 1。
情形2: a = 1. 如果w有偶数个 1, 则z有奇数个1。由归纳假设, (A,z) = B. 由转移表的DFA知 (A,w) = A. 如果w有奇数个 1, 则z有偶数个1。由归纳假设, (A,z) = A, 由转移表的DFA知 (A,w) = B. 因此这种情况下 (A,w) = A 当且仅当 w 有偶数个 1. 综合上述情形,命题得证。
P45 习题2.3.4 给出接受下列语言的非确定型有穷自动机。尝试尽可能多利用非确定性。 a)在字母表{0,1,...,9}上的串的集合,使得结尾数字在前面出现过。
c)0和1的串的集合,使得有两个0间隔的位置数是4的倍数。注意,0算是4的倍数。 答案
a) qs为初始状态,qf为终止状态,可一直停与qs,即尚未猜测。转移表/图如下所示。 记qi为已看到i并猜测i是结尾将要重复的数字,i=0,1,…,9。
q0 q1 ... q9 * qs c)
→qs q0 q1 q2 q3 q4 * qf
0 {q0} {qf} {q0,q2} {q0,q3} {q0,q4} {qf} {qf} 1 {qs} {q1} {q2} {q3} {q4} {q1} {qf}
0 {qf} {q1} ... {q9} {} 1 {q0} {qf} ... {q9} {} ... ... ... ... ... ... ... 9 {qs,q9} {q0} {q1} ... {qf} {}
→qs {qs,q0} {qs,q1}
正在阅读:
第1次作业06-26
质量经理高级研修班大纲08-14
人教版七年级下册数学期末试卷四07-12
空乘广播12-17
手术台就是阵地教学反思02-21
(目录)2017-2022年中国锂电池正极材料行业发展预测及投资咨询07-11
CNC雕刻机数控铣高速铣之间对比分析01-22
2013高考新北京卷文综地理解析版03-20
航空器发展简史04-15
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 作业
- 04 完善制度 创新机制 努力提高城乡困难群众医疗救助水平
- 一级减速器说明书
- 学校心理健康教育工作计划
- 管维良:三峡巫文化
- 德国ADS签证须知 - 图文
- 电工技术基础与技1
- 江津给水方案
- 2016石圪台煤矿地质类型划分报告 - 图文
- 红楼梦人物关系图
- 五年级数学上册第七单元数学广角植树问题2教案
- 煤检站磅房监控联网方案 - 图文
- 福建省莆田市2014-2015学年5月高三第三次月考理科综合试题(含答
- 2018上半年党风廉政建设工作总结3篇
- 川大17春《古代汉语(上)1537》17春在线作业2
- 2015年教师大比武总结 Microsoft Word 文档
- 吕河镇敖院小学素质教育实施方案
- 东北大学网络教育入学测试机考模拟题
- 如何设计青稞陈醋项目可行性研究报告(技术工艺+设备选型+财务概
- 湖北荆州数学-2014初中毕业学业考试试卷 - 图文
- 《书香润璞》校长报告定稿6月10日