形式语言与自动机理论蒋宗礼第二章参考答案Word文档下载推荐.docx
- 文档编号:3562561
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:41
- 大小:215.92KB
形式语言与自动机理论蒋宗礼第二章参考答案Word文档下载推荐.docx
《形式语言与自动机理论蒋宗礼第二章参考答案Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《形式语言与自动机理论蒋宗礼第二章参考答案Word文档下载推荐.docx(41页珍藏版)》请在冰点文库上搜索。
✓再次,编码,将详细设计的结果用文法符号的语言表示出来
✓最后,测试,找出边缘数据,特殊数据进行测试。
(8)按照文法的乔姆斯基体系,文法被分为几类?
各有什么样的特点?
分为四类:
✓文法G={V,T,P,S},对应的L(G)则为0型文法或短语结果文法。
✓如果对于
,均有
成立,则称G为1型文法或上下文有关文法,对应的L(G)称为1型语言。
成立,且
成立,则称G为2型文法,或上下文无关文法,对应的L(G)为2型语言。
,所有
均有:
成立,其中
则称G为3型文法,或正则文法,对应的L(G)称3型语言。
(9)什么叫左线性文法?
什么叫右线性文法?
什么叫线性文法
✓文法G={V,T,P,S},如果对于
成立,
则称G为线性文法。
则称G为右线性文法。
则称G为左线性文法。
(10)既然已经定义2-10中允许RL包含空语句
,那么定理2-6和定理2-7还有什么意义?
✓此为定义与定理的区别,定义2-10是针对文法G是RG的情况下,定义其产生式加上
后仍为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|AS
AS→SA
AS→0A
0A→S0
0AS→00
4:
AS→SA|ABB
ABB→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+id*id=>
归约:
(1)id+id*id<
=E+id*id<
=E+E*id<
=E+E*E<
=E+E<
=E
(2)id+id*id<
=E*id<
=E*E<
******************************************************************************
2.4设文法G的产生式集如下,试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约(02282081刘秋雯)
bB→bb
CB→BC
bC→bc
cC→cc
解:
推导一:
S→aBC|aSBC
aB→ab
S=>
aSBC
=>
aaSBCBC
aaaBCBCBC
aaabCBCBC
aaabBCCBC
aaabbCCBC
aaabbCBCC
aaabbBCCC
aaabbbCCC
aaabbbcCC
aaabbbccc
推导二:
=>
aaaBBCCBC
aaaBBCBCC
归约一、归约二分别为推导一和推导二的逆过程
5句子abeebbeeba的一个推导如下:
(陈伟芳学号?
?
)
S=>
aAa使用产生式SaAa
aSSa使用产生式ASS
abAbSa使用产生式SbAb
abSSbSa使用产生式ASS
abeSbSa使用产生式Se
abeebSa使用产生式Se
abeebbAba使用产生式SbAb
abeebbSSba使用产生式ASS
abeebbeSba使用产生式Se
abeebbeeba使用产生式Se
不能给出abeebbeeb的归约,因为由文法G中产生式推出的句子只有三种情况:
头尾都是a,头尾都是b,或者只有一个e,而abeebbeeb上面三个条件都不符合,所以它不是文法G的一个句子,当然也就不能给出它的一个归约了。
2.6设文法G的产生式集如下,请给出G的每个语法范畴代表的集合.
S→aSa|aaSaa|aAa
A→bA|bbbA|bB
B→cB|cC
C→ccC|DD
D→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}
7.给定如下文法,请用自然语言描述它们定义的语言。
(吴贤珺02282047)
⑴A→aaA│aaB
B→Bcc│D#cc
D→bbbD│#
该语言由四部分组成:
第一部分是偶数个a(至少有两个),第二部分是3的倍数个b(可以是0个),第三部分是两个“#”号,第四部分是偶数个c(至少有两个)。
⑵A→0B│1B│2B
B→0C│1C│2C
C→0D│1D│2D│0│1│2
D→0B│1B│2B
该语言的句子是字母表∑={0,1,2}上所有长度为3的倍数的字符串,且非空。
⑶A→0B│1B│2B
B→0C│1B│2B
C→0E│1D│2D│0│1│2
D→0C│1B│2B
E→0E│1D│2D│0│1│2
观察发现C和E所对应产生式右部是相同的。
所以将文法化简成如下的形式:
A→0B│1B│2B
C→0C│1D│2D│0│1│2
作出状态图如下:
A
B
C
D
0,1,2
1,2
F
可以看出从初始状态A到终态F,至少要经过A→B→C→F的过程,所以字符串的长度至少为3。
而且,到F只能经过C,如果到达C后走其它的路径,那么所经过的弧上的字符串都是以0为结尾,也就是要回到C,最后一个字符一定是0。
这样,该文法所确定的语言就是所有倒数第2个字符是0的串。
⑷S→aB│bA
A→a│aS│BAA
B→b│bS│ABB
由于该文法所确定的语言一时不易看出,可以先考虑简单的形式:
S→aB│bA
A→a│aS
B→b│bS
不难看出,该文法所确定的语言为所有由ab和ba组成的串,且非空。
这些串有一个特点,就是a和b的个数相等。
然后,把产生式A→BAA和B→ABB加回到原来的文法中,并且可以把这两个产生式看成是在左部的符号前分别加上串BA和AB。
不妨把它们看成一个符号C和D。
这样原文法可以改造成如下形式:
S→aB│bA
A→a│aS│CA
B→b│bS│DB
C→BA
D→AB
发现插入的C和D所导入的A和B是成对的,原文法所确定的语言可能就是字母表∑={a,b}上所有含有相同个a和b的字符串,且非空。
从上面简单形式的文法中已经看到,它所确定的字符串比a和b个数相同的所有串少的只是多个a或b连续的情况。
而加上产生式A→BAA和B→ABB后则刚好满足。
例如:
由S推出aB后,在B前“插入”D(即AB),可由AB中的A推出a,就得到aaBB,如此类推,最终可得该文法所接受的语言为:
字母表∑={a,b}上所有a和b个数相等的非空字符串。
8.设∑={0,1},请给出∑上的下列语言的文法
(1)所有以0开头的串
S→0A|0
A→0|1||0A|1A
(2)所有以0开头以1结尾的串
S→0A
A→1|0A|1A
(3)所有以11开头以11结尾的串
S→11A|11
A→11|0A|1A
(4)所有最多有一对连续的0或者最多有一对连续的1
1:
x中既没有成对的0,也没有成对的1
2:
x有一对连续的0
3:
x有一对连续的1
4:
x中既有一对连续的0,也有一对连续的1
S→A|B|C|D
A→ε|A’|A”
A’→0|01|01A’
A”→1|10|10A”
B→B’00B”
B’→1|01|1B’|01B’
B”→1|10|1B”10B”
C→C’11C”
C’→0|10|0C’|10C’
C”→0|01|0C”|01C”
D→E00F11H|P11G00K
E→1|1E’|E’
E’→01E’|E’
F→ε|10|10F//F以1开头,以0结尾;
不含连续0和连续1
H→0|H’0|H’
H’→01|01H’
P→0|0P’|P’
P’→10P’|10
G→ε|01|01G//G以0开头,以1结尾;
K→1|K’1|K’
K’→10|10K’
(5)所有最多有一对连续的0而且最多有一对连续的1
x只有一对连续的0,没有连续的1
y只有一对连续的1,没有连续的0
B→B’00B”’
B’→ε|1|01|01B’’|1B’’//B’是不含连续0,也不含连续1的串
B’’→01|01B’’
B”’→ε|1|10|10B””//B””是不含连续0,也不含连续1的串
B””→10|10B””
C→C’11C”’//C’是不含连续1,也不含连续0的串
C’→ε|0|10|0C”|10C”
C”→10|10C”
C”’→ε|0|01|01C””//C””是不含连续1,也不含连续0的串
C””→01|01C””
P’→10P’|10
(6)所有长度为偶数的串
S→01|10|00|11|01S|10S|00S|11S
(7)所有包含子串01011的串
S→X01011Y
X→ε|0X|1X
Y→ε|0Y|1Y
(8)所有含有3个连续0的串
S→X000Y
2.9设
,构造下列语言的文法。
(1)
解答:
(2)
(3)
S→aAB|aSAB
BA→AB
aB→ab
bA→ba
aA→aa
(4)
(5)
(6)
(7)
(8)
第10题参见下题:
11、给定RG
试分别构造满足下列要求的RGG,并证明你的结论。
P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1}
证明略。
P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1}
12.设文法G有如下产生式:
A→a│aS│bAA
B→b│bS│aBB
证明L(G)={ω│ω中含有相同个数的a和b,且ω非空}。
证:
观察发现A的产生式A→bAA中的bA可以用S来代替,同样B的产生式B→aBB中的aB也可以用S代替。
这样原来的文法可以化为如下的形式:
A→a│aS│SA
B→b│bS│SB
进一步地,可以把产生式A→aS中的S代换,把文法化为如下的形式:
A→a│aaB│abA│SA
B→b│baB│bbA│SB
下面,我们就对字符串ω的长度施归纳,同时证明以下三个命题成立。
⑴
ωiffω中含有相同个数的a和b,且ω非空。
⑵
ωiffω中含有a的个数比b的个数恰好多一个。
⑶
ωiffω中含有a的个数比b的个数恰好少一个。
第一步,由于只有A和B可以直接推出终结符,当ω的长度为1时,直接用A推出a或直接用B推出b。
直接用A推出a时,ω中a的长度为1,b的长度为0,含有a的个数比b的个数恰好多一个。
直接用B推出b时,b的长度为1,a的长度为0,ω中含有a的个数比b的个数恰好少一个。
这样,由S→aB│bA,知S推出的最短串,分别是ab和bb,其长度是2,并且a和b的个数相等。
第二步,假设上面的三个命题对长度为x的串成立。
对S,x=2n(n≥1);
对A和B,x=2n+1(n≥0)。
我们可以看到,由A或B推出的串长度如果要变长的话,必须把A或B用其除A→a或B→b之外的产生式代替。
i).考虑代替A的情形。
若A用aaB代替,由假设B中a的个数比b的个数恰好少一个,则aaB中a的个数比b的个数恰好多一个。
若A用abA代替,由假设A中a的个数比b的个数恰好多一个,则abA中a的个数比b的个数恰好多一个。
若A用SA代替,由假设A中a的个数比b的个数恰好多一个,而S中a和b的个数相等,则SA中a的个数仍然比b的个数恰好多一个。
ii).考虑代替B情形。
若B用baB代替,由假设B中a的个数比b的个数恰好少一个,则baB中a的个数比b的个数也恰好少一个。
若B用bbA代替,由假设A中a的个数比b的个数恰好多一个,则bbA中a的个数比b的个数恰好少一个。
若B用SB代替,由假设B中含有a的个数比b的个数恰好少一个,而S中a和b的个数相等,则SB中a的个数仍然比b的个数恰好少一个。
这样,命题
就得到了证明。
又由于S的产生式只有S→aB│bA,由以上两个命题,显然有命题
成立。
当我被上帝造出来时,上帝问我想在人间当一个怎样的人,我不假思索的说,我要做一个伟大的世人皆知的人。
于是,我降临在了人间。
我出生在一个官僚知识分子之家,父亲在朝中做官,精读诗书,母亲知书答礼,温柔体贴,父母给我去了一个好听的名字:
李清照。
小时侯,受父母影响的我饱读诗书,聪明伶俐,在朝中享有“神童”的称号。
小时候的我天真活泼,才思敏捷,小河畔,花丛边撒满了我的诗我的笑,无可置疑,小时侯的我快乐无虑。
“兴尽晚回舟,误入藕花深处。
争渡,争渡,惊起一滩鸥鹭。
”青春的我如同一只小鸟,自由自在,没有约束,少女纯净的心灵常在朝阳小,流水也被自然洗礼,纤细的手指拈一束花,轻抛入水,随波荡漾,发髻上沾着晶莹的露水,双脚任水流轻抚。
身影轻飘而过,留下一阵清风。
可是晚年的我却生活在一片黑暗之中,家庭的衰败,社会的改变,消磨着我那柔弱的心。
我几乎对生活绝望,每天在痛苦中消磨时光,一切都好象是灰暗的。
“寻寻觅觅冷冷清清凄凄惨惨戚戚”这千古叠词句就是我当时心情的写照。
最后,香消玉殒,我在痛苦和哀怨中凄凉的死去。
在天堂里,我又见到了上帝。
上帝问我过的怎么样,我摇摇头又点点头,我的一生有欢乐也有坎坷,有笑声也有泪水,有鼎盛也有衰落。
我始终无法客观的评价我的一生。
我原以为做一个着名的人,一生应该是被欢乐荣誉所包围,可我发现我错了。
于是在下一轮回中,我选择做一个平凡的人。
我来到人间,我是一个平凡的人,我既不着名也不出众,但我拥有一切的幸福:
我有温馨的家,我有可亲可爱的同学和老师,我每天平凡而快乐的活着,这就够了。
天儿蓝蓝风儿轻轻,暖和的春风带着春的气息吹进明亮的教室,我坐在教室的窗前,望着我拥有的一切,我甜甜的笑了。
我拿起手中的笔,不禁想起曾经作诗的李清照,我虽然没有横溢的才华,但我还是拿起手中的笔,用最朴实的语言,写下了一时的感受:
人生并不总是完美的,每个人都会有不如意的地方。
这就需要我们静下心来阅读自己的人生,体会其中无尽的快乐和与众不同。
“富不读书富不久,穷不读书终究穷。
”为什么从古到今都那么看重有学识之人?
那是因为有学识之人可以为社会做出更大的贡献。
那时因为读书能给人带来快乐。
自从看了《丑小鸭》这篇童话之后,我变了,变得开朗起来,变得乐意同别人交往,变得自信了……因为我知道:
即使现在我是只“丑小鸭”,但只要有自信,总有一天我会变成“白天鹅”的,而且会是一只世界上最美丽的“白天鹅”……
我读完了这篇美丽的童话故事,深深被丑小鸭的自信和乐观所折服,并把故事讲给了外婆听,外婆也对童话带给我们的深刻道理而惊讶不已。
还吵着闹着多看几本名着。
于是我给外婆又买了几本名着故事,她起先自己读,读到不认识的字我就告诉她,如果这一面生字较多,我就读给她听整个一面。
渐渐的,自己的语文阅读能力也提高了不少,与此同时我也发现一个人读书的乐趣远不及两个人读的乐趣大,而两个人读书的乐趣远不及全家一起读的乐趣大。
于是,我便发展“业务”带动全家一起读书……现在,每每遇到好书大家也不分男女老少都一拥而上,争先恐后“抢书”,当我说起我最小应该让我的时候,却没有人搭理我。
最后还把书给撕坏了,我生气地哭了,妈妈一边安慰我一边对外婆说:
“孩子小,应该让着点。
”外婆却不服气的说:
“我这一把年纪的了,怎么没人让我呀?
”大家人你一言我一语,谁也不肯相让……读书让我明白了善恶美丑、悲欢离合,读一本好书,犹如同智者谈心、谈理想,教你辨别善恶,教你弘扬正义。
读一本好书,如品一杯香茶,余香缭绕。
读一本好书,能使人心灵得到净化。
书是我的老师,把知识传递给了我;
书是我的伙伴,跟我诉说心里话;
书是一把钥匙,给我敞开了知识的大门;
书更是一艘不会沉的船,引领我航行在人生的长河中。
其实读书的真真乐趣也就在于此处,不是一个人闷头苦
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 自动机 理论 蒋宗礼 第二 参考答案