文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 形式语言与自动机理论-蒋宗礼-第三章参考答案
侵权投诉

形式语言与自动机理论-蒋宗礼-第三章参考答案

形式语言与自动机理论(第2版),清华大学出版社 北京工业大学计算机学院蒋宗礼老师主编

第三章作业答案

1.已知DFA M1与M2如图3-18所示。 (敖雪峰 02282068)

(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。

形式语言与自动机理论-蒋宗礼-第三章参考答案

qS

q0

1

形式语言与自动机理论-蒋宗礼-第三章参考答案

图3-18 两个不同的DFA

解答:(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3; M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;

(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:

M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]*

M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*}

******************************************************************************* 2.构造下列语言的DFA

形式语言与自动机理论-蒋宗礼-第三章参考答案

( 陶文婧 02282085 ) (1){0,1}*

,1

(2){0,

形式语言与自动机理论-蒋宗礼-第三章参考答案

1}

+

,1

(3){x|x {0,1}+且x中不含00的串}

(设置一个陷阱状态,一旦发现有00的子串,就进入陷阱状态)

第1页

你可能喜欢

  • 形式语言与自动机理论
  • 计算理论试题
  • 信号系统吴大正第四版
  • 图灵机模型
  • 理论复习
  • 离散数学屈婉玲

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email