仅供参考
《形式语言与自动机理论》期末考题 答卷
一、基本概念：
1、用归纳法证明：对于所有的 n≥0，n
4
- 4n
2
能被 3 整除。
证明：(1)基础：当 n=0 时，n
4
- 4n
2
=0,能被 3 整除；
(2)归纳：假设当 n=n 时，n
4
- 4n
2
能被 3 整除，
则 n=n+1 时，原式= (n+1)
4
– 4(n+1)
2
= n
4
- 4n
2
+6n
2
-3+4(n-1)n(n+1)
∵(n-1)n(n+1)为三个连续的整数的乘积
∴ 这三个数中一定有一个能被 3 整除，即 4(n-1)n(n+1)
又∵n
4
- 4n
2
、6n
2
-3 能被 3 整除
∴n
4
- 4n
2
+6n
2
-3+4(n-1)n(n+1)能被 3 整除，即(n+1)
4
– 4(n+1)
2
能被
3 整除
综上所述，对于所有的 n≥0，n
4
- 4n
2
能被 3 整除。
2、关系 R={(a, b), (a, c), (a, d), (d, c), (d, e)}的自反传递闭包 R
*
是什么？画出
表示 R
*
的有向图。
解：R*={(a,a),(a, b), (a, c), (a, d), (a,e),(b,b),(c,c),(d, c),(d,d), (d, e)}
R
*
的有向图
3、把下述正则表达式重写成表示同样集合的更简单的正则表达式：
(a) ⊙
*
∪a
*
∪b
*
∪(a∪b)
*
(b) (a∪b)
*
a(a∪b)
*
(c) (a
*
b)
*
∪(b
*
a)
*
解：(a) (a∪b)
*
(b) b
*
a(a∪b)
*
(c) (a∪b)
*
二、有一台非确定型有穷自动机，形式地，M=(
K,
,Δ,s,F
),其中:
K={q
0
,q
1
,q
2
,q
3
,q
4
,q
5
}，={a,b}，s=q
0
， F={q
5
}以及
Δ
如下：
Δ
={(q
0
,a,q
0
),(q
0
,b,q
0
),(q
0
,b,q
1
),(q
0
,a,q
3
),(q
1
,b,q
2
),(q
1
,a,q
4
),
(q
2
,e,q
5
),(q
3
,b,q
4
),(q
4
,b, q
5
),(q
5
,a,q
5
),(q
5
,b,q
5
)}
（1） 请画出该自动机的状态图；
王权大宝
- 粉丝: 17
- 资源: 6
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论10