形式语言与自动机理论教学参考书蒋宗礼.docx
- 文档编号:654484
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:23
- 大小:23.95KB
形式语言与自动机理论教学参考书蒋宗礼.docx
《形式语言与自动机理论教学参考书蒋宗礼.docx》由会员分享,可在线阅读,更多相关《形式语言与自动机理论教学参考书蒋宗礼.docx(23页珍藏版)》请在冰点文库上搜索。
形式语言与自动机理论教学参考书蒋宗
礼
形式语言与自动机理论教学参考书蒋宗礼篇一:
形式语言与自动机理论-蒋宗礼-第一章参考答案
第一章参考答案
1.1请用列举法给出下列集合。
(吴贤珺 02282047)
⑴你知道的各种颜色。
解:
{红,橙,黄,绿,青,蓝,紫}
⑵大学教师中的各种职称。
解:
{助教,讲师,副教授,教授}
⑶你所学过的课程。
解:
{语文,数学,英语,物理,化学,生物,历史,地理,政治}⑷你的家庭成员。
解:
{父亲,母亲,妹妹,我}⑸你知道的所有交通工具。
解:
{汽车,火车,飞机,轮船,马车}⑹字母表{a,b}上长度小于4的串的集合。
解:
{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺ 集合
{1,2,3,4}的幂集。
解:
{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},
{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}⑻所有的非负奇数。
解:
{1,3,5,7,?
}⑼0~100的所有正整数。
解:
{1,2,3,?
100}(10)
1~10之间的和为10的整数集合的集合。
解:
设所求的集合为
A,集合A中的元素为Ai(i=1,2,3,?
),Ai也是集合,Ai中的元素
在1~10之间,并且和为10。
根据集合元素的彼此可区分性,可
以计算出Ai中元素的最多个数,方法是:
把1开始的正整数逐个相加,直到等于10(即10=1+2+3+4),这样,Ai中最多有4个元素。
原因是:
从最小的1开始,每次加入新的元素都只依次增加1,
这样相加的和最小,要加到10,元素个数就最多。
求出最大的∣Ai∣=4后,再求出元素个数为3,2,1的集合就可以了。
故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},
{1,2,3,4}}
1.2请用命题法给出下列集合
2.
(1){x|0?
x?
100且x?
z}
(2){x|x?
{a,b}且|x|?
4}
(3){B|B?
{1,2,3,4}}
(4){L|L?
{a,b}*}
(5){x|x?
2n?
1,n?
N}
(6){(a,b)|a?
b?
10且a,b?
[4,9]}
(7){x|x?
{0,1},且x中0的个数是1的个数的两倍}
(8){x|x?
{0,1},且x中1的个数是10}(9){x|x?
{0,1},且x中倒数第十个字符为1}
|A||****
(10){A|?
xi?
A,xi?
[1,10],i?
[1,|A|],?
xi=10}
i?
1
1.3给出下列集合的幂集.(02282075 冯蕊)
(1)Φ
(2){Φ}
(3){Φ,{Φ}}
(4){ε,0,00}
(5){0,1}
解答:
(1){Φ}
(2){Φ,{Φ}}
(3){Φ,{Φ},{{Φ}},{Φ,{Φ}}}
(4){Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
(5){Φ,{0},{1},{0,1}}
1.4.列出集合{0,1,2,3,4}中 (褚颖娜 02282072)
(1)所有基数为3的子集
{0,1,2},{0,1,3},{0,1,4},{0,2,3,},{0,2,4},
.{1,2,3},{1,2,4},{1,3,4},{0,3,4},{2,3,4}
(2)所有基数不大于3的子集Ф,{0},{1},{2},{3},{4},{3,4},{2,4},{2,3},{1,4},
{1,3},{0,4},{0,3},{0,2},{1,2},{0,1},{0,1,2},
{0,1,3}
{0,1,4},{0,2,3,},{0,2,4},.{1,2,3},{1,2,4},
{1,3,4},{0,3,4},{2,3,4}
1.5解答:
1、3、8、10、11、12、16正确
1.6证明下列各题目 (02282081刘秋雯)
1)A=B,iffA是B的子集且B是A的子集证明:
充分条件:
∵A=B
则由集合相等的定义知对于任何x∈A,有x∈B
∴A为B的子集
同理,B为A的子集必要条件:
∵A为B的子集
∴对于任何x∈A,都有x∈B
又∵B为A的子集,
∴对于任何x∈B有,x∈A由集合相等的定义知,A=B
2)如果A为B的子集,则|A|〈=|B|证明:
A为B的子集,则对于任何x∈A
有x∈B,
∴存在一个集合C使B=A∪C 且A∩C为空集
则|B|=|A|+|C|
|C|〉=0
∴|A|〈=|B|
3)如果A为B的真子集,则|A|〈=|B|证明:
(1)当A为有穷集合时,因为A为B的真子集,且则对于任何x∈A
有x∈B,
且存在∈B的x,此x不∈A
∴存在一个非空集合C,使B=A∪C 且A∩C为空集则|B|=|A|+|C|且|C|〉=1
∴|A|〈|B|
(2)当A为无穷集合,因为A为B的真子集,则B一定也为无穷集合,|A|=∞,|B|=∞
∴|A|=|B|
综合
(1),
(2)所述,|A|=|B|
4)如果A是有穷集且A为B的真子集则|A|〈|B|证明:
见上题证明
(1)
5)如果A为B的子集,则对于任何x∈A,有x∈B
证明:
若A为B的子集,则由子集定义可知,对于任何x∈A,有
x∈B
6)如果A是B的真子集,则对于任何x∈A,有x∈B,并且存在x∈B,但x不
∈A
证明:
由真子集的定义可证
7)如果A为B的子集,B为C的子集,则A为C的子集证明:
A为B的子集,B为C的子集则对于任何x∈A,则x
都∈B,
且,又对于任何y∈B,则y∈C,∴对于任何x∈A,x∈C
∴A为C的子集
8)如果A为B的真子集,B为C的真子集,则A为C的真子
集
证明:
A为B的真子集,B为C的真子集则对于任何x∈A,则x都∈B,且,存在x∈B但次x不∈A,
又对于任何y∈B,则y∈C,存在y∈C但此y不∈B,
∴对于任何x∈A,x∈C,存在x∈C.x不∈A
∴A为C的真子集
9)如果A为B的子集,B为C的真子集,则A为C的真子集证明:
因为A为B的子集,B为C的真子集
则对于任何x∈A,x都∈B,且x都∈C
又对于任何y∈B,则y∈C,存在y∈C但此y不∈B,则y不
∈A
∴对于任何x∈A,x∈C,存在x∈C.x不∈A
∴A为C的真子集
10)如果A为B的真子集,B为C的子集,则A为C的真子集证明:
A为B的真子集,B为C的子集则对于任何x∈A,则x都∈B,且存在x∈B但次x不∈A,
又对于任何y∈B,则y∈C
∴对于任何x∈A,x∈C,存在x∈C.x不∈A
∴A为C的真子集11)如果A=B,则|A|=|B|证明:
A=B,则A与B所含元素相同
∴|A|=|B|
12)如果A为B的子集,B为C的真子集,或如果A为B的真
子集,B为C的子集,则A为C的真子集
证明:
证明见9,10
1.7 A = {1,2,3,4,5,6} B = {1,3,5} C = {2,4,6} U =
{0,1,2,3,4,5,6,7,8,9}
(1).A?
B
={1,3,5}=B
(2).(A?
B)?
C
={1,3,5}?
{2,4,6}
={1,2,3,4,5,6}=A(3).(A?
B)?
(U?
C)
={1,3,5}?
{0,1,3,5,7,8,9}={0,1,3,5,7,8,9}=C(4).A-B-C
={2,4,6}–{2,4,6}
=?
(5).A×B×C×?
=?
?
A×?
=?
(6).(A?
B)?
A?
C?
A
={1,3,5}?
{0,7,8,9}?
{0,7,8,9}
={0,1,3,5,7,8,9}= C
(7).A?
B?
A?
C=A?
B?
C=A?
{(a,b)|(a?
B,b?
C)或(a?
B,b?
C)或(a?
B,b?
C)}
={(a,b,c)|(a?
A,b?
B,c?
C)或(a?
A,b?
B,c?
C)或(a?
A,b?
B,c?
C)} (8).
A?
B?
(A?
B)?
C
=A?
A?
C
=A?
C
=A
={1,2,3,4,5,6}
形式语言与自动机理论教学参考书蒋宗礼篇二:
形式语言与自动机理论-蒋宗礼-第三章参考答案
第三章作业答案
1.已知DFA M1与M2如图3-18所示。
(敖雪峰
02282068)
(1)请分别给出它们在处理字符串1011001的过程中经过的状态序列。
(2)请给出它们的形式描述。
qSq01
图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的子串,就进入陷阱状态)
(4){x|x?
{0,1}*且x中不含00的串}
(可接受空字符串,所以初始状态也是接受状态)
(5){x|x?
{0,1}+且x中含形如10110的子串}
+
(6){x|x?
{0,1}且x中不含形如10110的子串}
(设置一个陷阱状态,一旦发现有00的子串,就进入陷阱状态)
(7){x|x?
{0,1}+且当把x看成二进制时,x模5和3同余,要求当x为0时,|x|=1,且x?
0
时,x的首字符为1}
1.以0开头的串不被接受,故设置陷阱状态,当DFA在启动状态读入的符号为0,则进
入陷阱状态
2.设置7个状态:
开始状态qs,q0:
除以5余0的等价类,q1:
除以5余1的等价类,q2:
除以5
余2的等价类,q3:
除以5余3的等价类,q4:
除以5余4的等价类,接受状态qt
(8){x|x?
{0,1}且x的第十个字符为1}
(设置一个陷阱状态,一旦发现x的第十个字符为0,进入陷阱状态)
+
(9){x|x?
{0,1}+且x以0开头以1结尾}
(设置陷阱状态,当第一个字符为1时,进入陷阱状态)
(10){x|x?
{0,1}+且x中至少含有两个1}
(11){x|x?
{0,1}+且如果x以1结尾,则它的长度为偶数;如果x以0结尾,则它的长度
为奇数}
可将{0,1}+的字符串分为4个等价类。
q0:
[?
]的等价类,对应的状态为终止状态 q1:
x的长度为奇且以0结尾的等价类
q2:
x的长度为奇且以1结尾的等价类 q3:
x的长度为偶且以0
结尾的等价类q4:
x的长度为偶且以1结尾的等价类
(12){x|x是十进制非负数}
4,9
5,6
,7,8,9
(13)?
(14)?
********************************************************
***********************
3
(1)(张友坤02282061)
?
={0,1}
Set(q0)={x | x?
?
*}
(2)
?
={0,1}
Set(q0)=?
Set(q1)={x | x?
?
+}
(3)
?
={0,1}
Set(q0)=?
Set(q1)={x | x?
?
+并且x中不含形如00的子串}Set(q2)={x
| x?
?
+并且x中不含形如00的子串}(4)
?
={0,1}
Set(q0)={x | x?
?
*并且x中不含形如00的子串 }Set(q1)
={x | x?
?
*并且x中不含形如00的子串} (5)
形式语言与自动机理论教学参考书蒋宗礼篇三:
形式语言与自动机理论-蒋宗礼-第二章参考答案
2.1回答下面的问题:
(周期律 02282067)
(1)在文法中,终极符号和非终极符号各起什么作用?
?
终结符号是一个文法所产生的语言中句子的中出现的字符,他决定了一个文法的产生语
言中字符的范围。
?
非终结符号又叫做一个语法变量,它表示一个语法范畴,文法中每一个产生式的左部至
少要还有一个非终结符号,(二,三型文法要求更严,只允许左部为一个非终结符号)他是推导或归约的核心。
(2)文法的语法范畴有什么意义?
开始符号所对应的语法范畴有什么特殊意义?
?
文法的非终结符号A所对应的语法范畴代表着一个集合L(A),此集合由文法产生式
中关于A的产生式推导实现的
?
开始符号所对应的语法范畴则为文法G={V,T,P,S}所产生的语言L(G)
={w|w?
T且S?
w}
(3)在文法中,除了的变量可以对应一个终极符号行的集
合外,按照类似的对应方法,一个字符串也可以对应一个终极符号行集合,这个集合表达什么意义?
?
字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合,为某个句
型的语言。
(4)文法中的归约和推导有什么不同?
?
推导:
文法G={V,T,P,S},如果?
?
?
?
P,?
?
?
(V
推导出了?
?
?
。
?
归约:
文法G={V,T,P,S},如果?
?
?
?
P,?
?
?
(V
约到?
?
?
。
?
这他们的定义,我个人理解两个概念从不同角度看待文法中的产生式,推导是自上而下
(从产生式的左边到右边),而归约是自下而上(从产生式的右边到左边),体现到具体实际中,如编译中语法分析时语法树的建立,递归下降,LL
(1)等分析法采用自开始符号向下推导识别输入代码生成语法树,对应的LR
(1),LALR等分析法则是采用自输入代码(相当于文法中语言的句子)自底向上归约到开始符号建立语法树,各有优劣。
(5)为什么要求定义语言的字母表上的语言为一个非空有穷集合?
?
非空:
根据字母表幂的定义:
**?
T),则称?
?
?
在G中**?
T),则
称?
?
?
在G中归?
0?
{?
},?
为字母表中0个字符组成的。
这样,当字
母
表中没有字符的情况,字母表也有一个元素,字母表为空就没有意义,而且,如果字母表为空,将无法定义其上的语言,使得理论体系不严密。
?
有穷:
我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言,在此基础上
我们才定义了字母表和语言,如果字母表为无穷的,他就违背了我们研究问题的初衷,这也使得研究失去意义
(6)任意给定一个字母表?
,该字母表上的语言都具有有穷描述吗?
为什么?
?
错误,因为一个字母表上有不可数无穷多个语言,而有穷表示只可能是可数无穷多个,
又因为不可数无穷集和可数无穷集不是一一对应的,所以存在这样的语言,他不存在有穷表示。
(7)请总结一下,在构造文法时,可以从哪几个方面入手?
?
我们可以将其类比于软件工程中的概念:
-)
?
首先,也是最重要的一点,需求分析,我们需要知道需要构造的语言的特点,具体表现
形式,以及一些需要注意的细节,通过一些特例提炼特点。
?
其次,概要设计,将语言从具体中抽象到符号上,按照其特
性将其划分类别。
?
再次,详细设计,将每一部分抽象的成果
具体化,将所有细节符号化
?
再次,编码,将详细设计的结果用文法符号的语言表示出来
?
最后,测试,找出边缘数据,特殊数据进行测试。
(8)按照文法的乔姆斯基体系,文法被分为几类?
各有什么样的特点?
分为四类:
?
文法G={V,T,P,S},对应的L(G)则为0型文法或短语结果文法。
?
如果对于?
?
?
?
?
P,均有?
?
成立,则称G为1型文法或上下文有关文法,
?
?
成立,且?
?
V成立,则称G为2型文法,或对应的L(G)称为1型语言。
?
如果对于?
?
?
?
?
P,均有
上下文无关文法,对应的L(G)为2型语言。
?
如果对于?
?
?
?
?
P,所有?
?
?
均有:
A?
w或A?
wB成立,其中
A,B?
V,w?
T?
则称G为3型文法,或正则文法,对应的L(G)称3型语言。
(9)什么叫左线性文法?
什么叫右线性文法?
什么叫线性文
法
A?
w或A?
wBx?
文法G={V,T,P,S},如果对于?
?
?
?
?
P,所
有?
?
?
均有:
成立,A,B?
V,x,w?
T,则称G为线性文法。
?
文法G = {V,T,P,S},如果对于?
?
?
?
?
P,所有?
?
?
均有:
A?
w或A?
wB
成立,其中A,B?
V,w?
T,则称G为右线性文法。
?
文法G = {V,T,P,S},如果对于?
?
?
?
?
P,所有?
?
?
均有:
A?
w或A?
Bw
成立,其中A,B?
V,w?
T,则称G为左线性文法。
(10)既然已经定义2-10中允许RL包含空语句?
,那么定理
2-6和定理2-7还有什么意义?
?
?
*
?
此为定义与定理的区别,定义2-10是针对文法G是RG的情况下,定义其产生式加上
S?
?
后仍为RG,G的语言仍为RL,而定理2-6和定理2-7针
对的前提条件是如果L为RL,他们都是通过定义2-10证明得到的,可以在以后的推论中直接应用的。
********************************************************
***********************
2.设L={0n|n≥1},试构造满足要求的文法G.
(1)G是RG.
(2)G是CFG,但不是RG.
(3)G是CSG,但不是CFG.
(4)G是短语结构文法,但不是CSG.
解答:
1:
S→0|0S
2:
S→0|0S|SS
3:
S→0|0S|ASAS→SAAS→0A0A→S0
0AS→00
4:
S→0|0S|ASAS→SA|ABBABB→AS
AB→A|ε
********************************************************
***********************
3.设文法G的产生式集如下,试给出句子id+id*id的两个不同的推导和两个不同的归约E→id|c|+E|-E|E+E|E-
E|E*E|E/E|E**E|Fun(E) (褚颖娜02282072)推导:
(1)E=E+E=E+E*E=E+E*id=E+id*id=id+id*id
(2)E=E*E=E*id=E+E*id=E+id*id=id+id*id
归约:
(1)id+id*id=E+id*id=E+E*id=E+E*E=E+E=E
(2)id+id*id= E+id*id= E+E*id=E*id= E*E=E
********************************************************
**********************
2.4 设文法G的产生式集如下,试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约(02282081刘秋雯)bB→bb
CB→BC
bC→bccC→cc
解:
推导一:
S→aBC|aSBCaB→abS=aSBC
=aaSBCBC
=aaaBCBCBC
=aaabCBCBC
=aaabBCCBC
=aaabbCCBC
=aaabbCBCC
=aaabbBCCC
=aaabbbCCC
=aaabbbcCC
=aaabbbccc
推导二:
S=aSBC
=aaSBCBC
=aaaBCBCBC
=aaaBBCCBC
=aaaBBCBCC
=aaabbCBCC
=aaabbBCCC
=aaabbbCCC
=aaabbbcCC
=aaabbbccc
归约一、归约二分别为推导一和推导二的逆过程
********************************************************
***********************5句子abeebbeeba的一个推导如下:
(陈伟芳学号?
?
)S=aAa 使用产生式S?
aAa
=aSSa使用产生式A?
SS
=abAbSa 使用产生式S?
bAb
=abSSbSa使用产生式A?
SS
=abeSbSa 使用产生式S?
e
=abeebSa 使用产生式S?
e
=abeebbAba使用产生式S?
bAb
=abeebbSSba 使用产生式A?
SS
=abeebbeSba 使用产生式S?
e
=abeebbeeba使用产生式S?
e
不能给出abeebbeeb的归约,因为由文法G中产生式推出的句子只有三种情况:
头尾都是a,头尾都是b,或者只有一个e,而abeebbeeb上面三个条件都不符合,所以它不是文法G的一个句子,当然也就不能给出它的一个归约了。
********************************************************
***********************
2.6 设文法G的产生式集如下,请给出G的每个语法范畴代表的集合.
S→aSa|aaSaa|aAaA→bA|bbbA|bBB→cB|cCC→ccC|DDD→dD|d
解:
set(D)={d}+
set(C)={c2ndm|m≥2n≥0}set(B)={cndm|m≥2n≥1}set(A)={bpcndm|p≥1,m≥2,n≥1}
set(S)={aqbpcndmaq|p≥1,m≥2,n≥1,q≥1}
**********************************
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 自动机 理论 教学 参考书 蒋宗礼