形式语言与自动机理论蒋宗礼第二章参考答案.docx

形式语言与自动机理论蒋宗礼第二章参考答案.docx

《形式语言与自动机理论蒋宗礼第二章参考答案.docx》由会员分享，可在线阅读，更多相关《形式语言与自动机理论蒋宗礼第二章参考答案.docx（21页珍藏版）》请在冰点文库上搜索。

形式语言与自动机理论蒋宗礼第二章参考答案

2．1回答下面的问题：

（周期律02282067）

（1）在文法中，终极符号和非终极符号各起什么作用？

✓终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语言中字符的范围。

✓非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。

（2）文法的语法范畴有什么意义？

开始符号所对应的语法范畴有什么特殊意义？

✓文法的非终结符号A所对应的语法范畴代表着一个集合L（A），此集合由文法产生式中关于A的产生式推导实现的

✓开始符号所对应的语法范畴则为文法G={V，T，P，S}所产生的语言L（G）={

}

（3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？

✓字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句型的语言。

（4）文法中的归约和推导有什么不同？

✓推导：

文法G={V，T，P，S}，如果

则称

在G中推导出了

。

✓归约：

文法G={V，T，P，S}，如果

则称

在G中归约到

。

✓这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下（从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL

（1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR

（1），LALR等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。

（5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？

✓非空：

根据字母表幂的定义：

为字母表中０个字符组成的。

这样，当字母表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。

✓有穷：

我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义

（6）任意给定一个字母表

，该字母表上的语言都具有有穷描述吗？

为什么？

✓错误，因为一个字母表上有不可数无穷多个语言，而有穷表示只可能是可数无穷多个，又因为不可数无穷集和可数无穷集不是一一对应的，所以存在这样的语言，他不存在有穷表示。

（7）请总结一下，在构造文法时，可以从哪几个方面入手？

✓我们可以将其类比于软件工程中的概念:

-）

✓首先，也是最重要的一点，需求分析，我们需要知道需要构造的语言的特点，具体表现形式，以及一些需要注意的细节，通过一些特例提炼特点。

✓其次，概要设计，将语言从具体中抽象到符号上，按照其特性将其划分类别。

✓再次，详细设计，将每一部分抽象的成果具体化，将所有细节符号化

✓再次，编码，将详细设计的结果用文法符号的语言表示出来

✓最后，测试，找出边缘数据，特殊数据进行测试。

（8）按照文法的乔姆斯基体系，文法被分为几类？

各有什么样的特点？

分为四类：

✓文法G={V，T，P，S}，对应的Ｌ（Ｇ）则为０型文法或短语结果文法。

✓如果对于

，均有

成立，则称Ｇ为１型文法或上下文有关文法，对应的Ｌ（Ｇ）称为１型语言。

✓如果对于

，均有

成立，且

成立，则称Ｇ为２型文法，或上下文无关文法，对应的Ｌ（Ｇ）为２型语言。

✓如果对于

，所有

均有：

成立，其中

则称Ｇ为３型文法，或正则文法，对应的Ｌ（Ｇ）称３型语言。

（9）什么叫左线性文法？

什么叫右线性文法？

什么叫线性文法

✓文法G={V，T，P，S}，如果对于

，所有

均有：

成立，

则称Ｇ为线性文法。

✓文法G={V，T，P，S}，如果对于

，所有

均有：

成立，其中

则称Ｇ为右线性文法。

✓文法G={V，T，P，S}，如果对于

，所有

均有：

成立，其中

则称Ｇ为左线性文法。

（10）既然已经定义2-10中允许RL包含空语句

，那么定理2-6和定理2-7还有什么意义？

✓此为定义与定理的区别，定义2-10是针对文法Ｇ是ＲＧ的情况下，定义其产生式加上

后仍为ＲＧ，Ｇ的语言仍为ＲＬ，而定理2-6和定理2-7针对的前提条件是如果Ｌ为ＲＬ，他们都是通过定义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：

S→0|0S|AS

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+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→bc

cC→cc

解：

推导一：

S→aBC|aSBC

aB→ab

S=>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|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

B→0C│1B│2B

C→0C│1D│2D│0│1│2

D→0C│1B│2B

作出状态图如下：

可以看出从初始状态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结尾；不含连续0和连续1

K→1|K’1|K’

K’→10|10K’

（5）所有最多有一对连续的0而且最多有一对连续的1

1：

x中既没有成对的0，也没有成对的1

2：

x只有一对连续的0，没有连续的1

3：

y只有一对连续的1，没有连续的0

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|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””

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结尾；不含连续0和连续1

K→1|K’1|K’

K’→10|10K’

（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

X→ε|0X|1X

Y→ε|0Y|1Y

*******************************************************************************

2.9设

，构造下列语言的文法。

（1）

。

解答：

。

（2）

。

解答：

。

（3）

。

解答：

S→aAB|aSAB

BA→AB

aB→ab

bB→bb

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有如下产生式：

（吴贤珺02282047）

S→aB│bA

A→a│aS│bAA

B→b│bS│aBB

证明L（G）＝{ω│ω中含有相同个数的a和b，且ω非空}。

证：

观察发现A的产生式A→bAA中的bA可以用S来代替，同样B的产生式B→aBB中的aB也可以用S代替。

这样原来的文法可以化为如下的形式：

S→aB│bA

A→a│aS│SA

B→b│bS│SB

进一步地，可以把产生式A→aS中的S代换，把文法化为如下的形式：

S→aB│bA

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之外的产生式代替。

）.考虑代替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的个数恰好多一个。

）.考虑代替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的个数恰好少一个。

这样，命题

ωiffω中含有a的个数比b的个数恰好多一个。

ωiffω中含有a的个数比b的个数恰好少一个。

就得到了证明。

又由于S的产生式只有S→aB│bA，由以上两个命题，显然有命题

ωiffω中含有相同个数的a和b，且ω非空。

成立。