第2章 作业及参考答案

形式语言与自动机理论课程是计算机科学与技术专业的一门很基础的课程。这套课件由于各种原因,我以后可能不再用了。但这份付出了我心血的成果愿意献出来,供大家共享。

4题：文法G的产生式集合如下，试给出句子aaabbbccc的一个推导和一个归约

S→aBC | aSBC

CB→BC

aB→ab

bB→bb

bB→b

bC→bc

cC→c

cC→cc

6题：文法G的产生式集合如下，请给出G中每个语法范畴代表的集合

S→aSa|aaSaa|aAa

A→bA|bbbA|bB

B→cB|cC

C→ccC|DD

D→dD|d

7题: 给定如下文法，请用自然语言描述它们定义的语言

（4）

S→aB|bA

A→a|aS|BAA

B→b|bS|ABB

8题: 设∑={0,1}, 请给出∑上下列语言的文法

（3）所有以11开头, 以11结尾的串;

（6）所有长度为偶数的串

9题: 设∑={a,b,c}, 构造下列语言的文法

（2）L2={anbm|n,m≥1}

（3）L3={anbnan|n≥1}

（4）L4={anbmak|n,m,k≥1}

（6）L6={xwxT| x,w∈∑+}

（7）L7={w | w = wT, w∈∑+}

补充：对给定RG

S→abA|baB

A →abA|ab

B →baB|ba

构造等价文法，新文法的产生式形如：

A→a，A→aB，A,B∈V，a∈T

形式语言与自动机理论课程是计算机科学与技术专业的一门很基础的课程。这套课件由于各种原因,我以后可能不再用了。但这份付出了我心血的成果愿意献出来,供大家共享。

参考答案

4、文法G的产生式集合如下，试给出句子aaabbbccc的一个推导和一个归约

S→aBC | aSBC

CB→BC

aB→ab

bB→bb

bB→b

bC→bc

cC→c

cC→cc

答：

S aSBC

aaSBCBC

aaaBCBCBC

aaabCBCBC

aaabBCCBC

aaabbCCBC

aaabbCBCC

aaabbBCCC

aaabbbCCC

aaabbbccC

aaabbbccc

6、文法G的产生式集合如下，请给出G中每个语法范畴代表的集合

S→aSa|aaSaa|aAa

A→bA|bbbA|bB

B→cB|cC

C→ccC|DD

D→dD|d

解：(注意方法)

Set(D)= {dm| m≥1}

set(C)= {c2ndm| n≥0,m≥2}(注意：d只要大于2，不一定是偶数，可以没有c)

set(B)= {cndm| n≥1,m≥2}

set(A)= {bkcndm| k≥1,n≥1,m≥2}

set(S)= {apbkcndmap| p≥1,k≥1,n≥1,m≥2}

问题：

不可写作：S={……}

讨论：

S anAan

anbmBan

anbmcxCan***

anbmcxDDan

anbmcxdyan**

S {anbmcxdyan|n,m,x 1,y 2} ------06级张言飞

形式语言与自动机理论课程是计算机科学与技术专业的一门很基础的课程。这套课件由于各种原因,我以后可能不再用了。但这份付出了我心血的成果愿意献出来,供大家共享。

7（4）、给定如下文法，请用自然语言描述它们定义的语言

S→aB|bA

A→a|aS|BAA

B→b|bS|ABB

解：该文法定义字母表∑={a,b}上的所有a和b的个数相等的字符串构成的语言。

分析：若仅考虑产生式S→aB|bA, A→a|aS, B→b|bS，可知文法确定由ab和ba产生的非空串，如abbaba、abbabaab等，加入产生式A→BAA和B→ABB后，可视为在原有A的前面加上BA及在原有B的前面加上AB，这样A、B的出现是成对的，实际上加入这两个产生式的作用就是使连续的多个a和b，如aaabbb成为可能。所以，该文法产生a、b个数相同的非空字符串。

或：先改变文法后再分析

S→aB|bA

A→a|aS|CA

B→b|bS|DB

C→BA

D→AB -----------06级付海静，黄雪璨

付海静

8、设∑={0,1}, 请给出∑上下列语言的文法

（3）所有以11开头, 以11结尾的串;

解：S→11A11，A→ε| 0A | 1A

或：S→11|111|11A11，A→ε| 0A | 1A

或：S→11A，A→11 | 0A | 1A-----05级李祖玄

或：S→11|11A，A→11 | 0A | 1A-----06级周潺潺

或：S→11A11，A→AA|0|1|ε------05级王士卫（也行但不好）

或：S→11A11，A→BA，B→0|1|ε------05级刘亮

（6）所有长度为偶数的串

解：S→0A | 1A，A→ 0 | 1 | 0S | 1S

或：S→ASA | AA|ε，A→ 0 | 1 ----05级张士光

或：S→SA | A，A→00 |01|10 |11 ----06级曹守印

或：S→ASA |ε，A→ 0 | 1 ----05级吴利青

或：S→00S|01S|10S|11S|ε----05级岳宝

或：S→0A|1A |ε，A→0|1|0B|1B, B→0A|1A ----05级李祖玄

9、设∑={a,b,c}, 构造下列语言的文法

（2）L2={anbm|n,m≥1}

解：S→AB，A→a| aA ，B→b| bB

或：S→aS|aA，A→b|bA

或：S→aAb，A→aAB|ε, B→b| bB|ε---05级崔卫华

或：S→aAb，A→aA|aB|ε, B→bB|ε---06级李更林

或：S→aAb，A→aA|Ab|ε---06级张力强（很简洁，但忽左忽右，也不好）

形式语言与自动机理论课程是计算机科学与技术专业的一门很基础的课程。这套课件由于各种原因,我以后可能不再用了。但这份付出了我心血的成果愿意献出来,供大家共享。

错了但很有意思的解：S→aS|Sb|a|b（错误原因：L2={anbm|n,m≥0且n+m≥2}）-----05级于文斐

（3）L3={anbnan|n≥1}

解：由产生L={anbncn|n≥1}的文法，有

S aBA | aSBA

AB BA

aB ab

bB bb

bA ba

aA aa

（4）L4={anbmak|n,m,k≥1}

解：S→ABA，A→a| aA ，B→a| aB

或：S→aS|aA，A→bB|bA，B→a| aB

或：S→aAa，A→aA|Aa|B，B→Bb|b------------06级张力强，岳光同

（6）L6={xwxT| x,w∈∑+}

解：S→aSa|bSb|cSc| aAa|bAb|cAc，A→a| b | c | aA | bA | cA 错解：S→aAa|bAb|cAc，A→a|b|c|aA|bA|cA

错解：S→A|aSa|bSb|cSc| aAa|bAb|cAc，A→a| b | c | aA | bA | cA

（7）L7={w | w = wT, w∈∑+}

解：S→a|b|c|aa|bb|cc|aSa|bSb|cSc

或：S→a|b|c|aAa|bAb|cAc, A→S|ε -------------06级陈建伟 错解：S→a|b|c| aSa|bSb|cSc

补充题，对给定RG

S →abA|baB

A →abA|ab

B →baB|ba

构造等价文法，新文法的产生式形如：

A→a，A→aB，A,B∈V，a∈T

解：构造得

S →aA’|bB’

A’ →bA

B’ →aB

A →aA’’

A’’ →bA|ab

B →bB’’

B’’ →aB|ba

本文来源：https://www.bwwdw.com/article/pd3i.html