没有合适的资源?快使用搜索试试~ 我知道了~
首页Introduction to Automata Theory, Languages, and Computation(Second Edition)中文答案
资源详情
资源评论
资源推荐
!
" ##
$!
%&'
! ( )
*
杠杆可能出现 + 种情况,影响着最终状态。并且也要说明,前面一个大理石球是否从 , 滚
出,也就是说,前一个输入是否被接受。令 代表向左方的状态(如图表), 代表向右
方。这三个杠杆的每一个状态都可以用三个数( 或 )组成的序列表示。这个序列后面
跟着字母 或者 。 代表接受状态, 代表拒绝状态。' 种可能的状态中,只有 ( 种是
从初始状态 可达的。下面它的有穷自动机的转移表。
A B
-
.
/
/
/
/
/
/
0
!
证明:通过对1!1进行归纳,来证明 "!2 "!,具体过程如下:
3*40
56
!5%!
0!
75
基础* 2 ,则 !28。那么需证 "2 "8,记 2 命题变为
2 8由 的定义知这显然成立。
4*9:
!0
7*
归纳*假设命题对于比
短的串成立且 其中 是 的结尾符号。
到 的变换总结在下表中*
Expression 表达式 Reason 原因
开始
!由假设
,5
的定义把 看作是一个状态
4!归纳假设
,5 的定义
;
0
7
状态 93,< 分别表示以10和 结尾的串的状态。
0 1
-
.9
3 9
3< 9
/<< 9
'
0:7
! !$
#---%
!=0!
; !
!=
!= (;
!0
!!
对于一个二进制整数,如果读入一个比特0,其值等于原数乘以2;否则等于原数乘
以2再加以 。而任意一个数均可写成形如 ,其中 任意, >2>2;,那么输
入 ,原数变为 ,由于 是 = 的倍数,因此 除以5的
余数与 相同。输入 ,则得 =?? 类似。因此对于所有的数只要记住它被5除的
余数就可以。由于 是 ( 或者 ;我们可以容易得到该 ,@9 的转移表,具体如下:
0
!=
其中状态 代表输入串被5除的余数 的状态。
0 1
-
./"
"
"
"
"
"(
"
"
;
"
"(
"
"
";
"
(
";
(
0
#!
AA
##45:B
)5
0*
但是上述自动机仍接受以0开头的字符串。因为题目要求只接受以1开头的串,可增加一
个初始状态 和“死亡状态”。在状态初始状态 若看到1,则转到状态 ;若看到0
则直接转到状态 ,识别终止。所求自动机如下*
0 1
-. "
/"
"
"
"
"
"(
"
"
;
"
"(
"
"
";
"
(
";
C
@!
3* 20
!
!
!
4*!0
!
D!
!E2
!
!
证明:通过对 长度的归纳证明。
基础*若 2,则 是一个符号,此时需证
!
而对于单个符号扩
展转移函数 与转移函数
的作用
是一样的,得证。
归纳*令 假设对于 7 命题
!
成立。那么
!
D由归纳假设E2
!
!
;
F:
!
"#$%
!
!
&'"$()"$*+%$%$#%%
#
!
&
,-%#""("$./"$&
'$*+%$,*("""("$!%#0&"&
1234#
!
&2$.
5"+"&&
#
#
!
6"
$*+/"%"7
!
67&
b) 是属于 9的非空串,也即串 被接收,因此
!
,则由 知
!
"
。现在通过对 #的归纳来证明
#
!
。
基础*#时,需证
!
,由已知可得。
归纳:假设对于 :- 命题成立,也就是说,
#
!
。由练习
#
#
!
D由归纳假设E
!
D由E。
5"+"&&
8"*%(%$"))"""$*("%!9""$"/"$"%%
"++"$.$")"+"&'$"$*+%$%$ %%
!$%$)!$"/"$$*("%!9&
, &8"$""($.*")$"/"$$*("%!9
$(")"%9$ &
'$*+%$,*("""("$!%$.%"$&8"$
""""%&
",&'!$"/"$$*("%!9%%"&"$*+/"
%" &8"$%$%!"-"))* &'!
$%$*("%!9"$%%"&"$*+/"%"
$"$%$%!"-"))*&8*$
+"!$%$)!$"/"$$*("%!9&
",&'!$"/"$$*("%!9"$$%$*("%!
9&"$*+/"%"&8"$%$%!"-"))
*&'!$%$*("%!9"$$"/"$$*("
%!9&"$*+/"%"$"$%$%!"
-"))*&8*$+""))!$
%$)!$"/"$$*("%!9&
这个自动机表示,状态 9 表示偶数个 ,状态 3 表示奇数个 ,不管串有偶数个还是奇数
个 ,都会被接受。当且仅当串 中有偶数个 时,
&
。用归纳法证明如下
=
剩余63页未读,继续阅读
huangjunhimilyhuang
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 数据结构1800题含完整答案详解.doc
- 医疗企业薪酬系统设计与管理方案.pptx
- 界面与表面技术界面理论与表面技术要点PPT学习教案.pptx
- Java集合排序及java集合类详解(Collection、List、Map、Set)讲解.pdf
- 网页浏览器的开发 (2).pdf
- 路由器原理与设计讲稿6-交换网络.pptx
- 火电厂锅炉过热汽温控制系统设计.doc
- 企业识别CIS系统手册[收集].pdf
- 物业管理基础知识.pptx
- 第4章财务预测.pptx
- 《集成电路工艺设计及器件特性分析》——实验教学计算机仿真系.pptx
- 局域网内共享文件提示没有访问权限的问题借鉴.pdf
- 第5章网络营销策略.pptx
- 固井质量测井原理PPT教案.pptx
- 毕业实习总结6篇.doc
- UGNX建模基础篇草图模块PPT学习教案.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论5