形式语言与自动机理论期末考试答卷（仅供参考）.pdf
5星 · 超过95%的资源 需积分: 50 192 浏览量
2019-05-20
10:24:20
上传
评论 4
收藏 742KB PDF 举报 
仅供参考
《形式语言与自动机理论》期末考题 答卷
一、基本概念：
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
- 1
- 2
前往页