第2章作业及参考答案
- 格式：docx
- 大小：14.93 KB
- 文档页数：4
4 题：文法 G 的产生式集合如下，试给出句子 aaabbbccc 的一个推导和一个归约
ST aBCIaSBC
CB T BC
aBtab
bBtbb
bBtb
bCtbc
cCtc
cCtcc
6 题：文法 G 的产生式集合如下，请给出 G 中每个语法范畴代表的集合
StaSaIaaSaaIaAa
AtbAIbbbAIbB
BtcBIcC
Ct ccCIDD
DtdDId
7 题 : 给定如下文法，请用自然语言描述它们定义的语言
(4)
StaBIbA
AtaIaSIBAA
BtbIbSIABB
8题：设刀={0,1},请给出刀上下列语言的文法
(3)所有以 11 开头 , 以 11 结尾的串 ;
(6)所有长度为偶数的串
9题：设刀={a,b,c},构造下列语言的文法
(2) L2={ anbm|n,m》1}
(3) L3={ anbnan|n》1}
(4) L4={a nbmak|n,m,k > 1}
(6) L6={xwx T| x,w +}
(7) L?={w | w = w T, w +}
补充：对给定 RG
St abAIbaB
A t abAIab
B t baBIba
构造等价文法，新文法的产生式形如：
ATa, ATaB, A,B € V , a€ T
参考答案
4、文法G的产生式集合如下，试给出句子
ST aBC|aSBC
CB T BC
aB T ab
bB T bb
bB T b
bC T be
cC T e
eC T ee
答：
S 二 aSBC
=aaSBCBC
=aaaBCBCBC
=aaabCBCBC
=aaabBCCBC
=aaabbCCBC
=aaabbCBCC
=aaabbBCCC
=aaabbbCCC
=aaabbbeeC
=aaabbbeee
6、文法G的产生式集合如下，请给出
ST aSa|aaSaa|aAa
A T bA|bbbA|bB
B T CB|CC
CT CCC|DD
D T dD|d
解：(注意方法)
Set(D)= {d m| m> 1} set(C)= {e 2ndm| n>
0,m > 2}(注意： aaabbbeee的一个推导和一个归约
G中每个语法范畴代表的集合
d只要大于
n m set(B)= {e d | n> 1,m> 2}
set(A)= {b kendm| k> 1,n》1,m>2}
set(S)= {a pbkendmap| p> 1,k > 1, n> 1,m > 2} 问题： 2,不一定是偶数，可以没有 e)
不可写作：S={……}
讨论：
*
n n S= a Aa *
n i m f n =a b Ba
*
二 anbmexCan
*
n ■ m x_ — =a b e DDa
5 anbmexd yan
n - m x - y n S ={a b e d a | n,m, x -1,y -2} 06级张言飞 7（ 4）、给定如下文法，请用自然语言描述它们定义的语言
ST aB|bA
A T a|aS|BAA
Btb|bS|ABB
解：该文法定义字母表刀 ={a,b}上的所有a和b的个数相等的字符串构成的语言。
分析：若仅考虑产生式 STaB|bA, A Ta|aS, BTb|bS,可知文法确定由ab和ba产生的非空串， 女口
abbaba、abbabaab等，加入产生式 ATBAA 和BTABB后，可视为在原有 A的前面 加上BA及在原有B的前面加上 AB，这样A、B的出现是成对的，实际上加入这两个 产生式的作用就是使连续的多个 a和b，女口 aaabbb成为可能。所以，该文法产生 a、b
个数相同的非空字符串。
或：先改变文法后再分析
StaB|bA
At a|aS|CA
Btb|bS|DB
CtBA
DtAB ---------- 06 级付海静，黄雪璨 付海静
8、设刀={0,1},请给出刀上下列语言的文法 （3）所有以 11 开头 , 以 11 结尾的串 ;
解： ST 11A11 , A T £ | 0A | 1A
或： ST 11|111|11A11, A T £ | 0A | 1A
或： St11A， At11 | 0A | 1A -------- 05 级李祖玄
或：
St11|11A， At11 | 0A | 1A -------- 06 级周潺潺
或： ST 11A11 , AT AA|0|1| £ ——05级王士卫（也行但不好）
或： ST 11A11 , AT BA , BT 0|1| £ ——05 级刘亮
6）所有长度为偶数的串
解： St0A | 1A， At 0 | 1 | 0S | 1S
或： ST ASA | AA| £ , AT 0 | 1 ----05 级张士光
或： StSA | A， At00 |01|10 |11 ------ 06 级曹守印
或： ST ASA | £ , A T 0 | 1 ----05 级吴利青
或：ST 00S|01S|10S|11S|g ----05 级岳宝
或：ST 0A|1A | £ , AT 0|1|0B|1B, B T0A|1A ----05 级李祖玄
9、设刀={a,b,c},构造下列语言的文法
（2） L2={a nbm|n,m > 1}
解： StAB， Ata| aA ， Btb| bB
或： StaS|aA， Atb|bA
或：ST aAb , AT aAB| £ , BT b| bB| £ ---05 级崔卫华
或：ST aAb , A T aA|aB| £ , BT bB| £ ---06 级李更林
或：ST aAb , AT aA|Ab|「--06级张力强（很简洁，但忽左忽右，也不好）
错了但很有意思的解： ST aS|Sb|a|b （错误原因：L2={anbm|n,m》0且n+m > 2}） —05级于
文斐
(3) L3={anbnan|n> 1} 解: 由产生L={a nbncn|n》1}的文法，有
S 、aBA|aSBA
AB —； BA
aBr ab
bBr bb
bAr ba
aAr aa
(4) L4={a nbmak|n,m,k > 1}
解：ST ABA , A T a| aA , BT a| aB
或：ST aS|aA, AT bB|bA , BT a| aB
或：ST aAa, AT aA|Aa|B , B T Bb|b ---------------
(6) L6={xwx T| x,w €刀 +}
解：ST aSa|bSb|cSc| aAa|bAb|cAc, AT a| b | c | aA | bA | cA 错解：ST aAa|bAb|cAc , A
Ta|b|c|aA|bA|cA
错解：STA|aSa|bSb|cSc| aAa|bAb|cAc , A T a| b | c | aA | bA | cA
(7) L7={W | w = w T, w +}
解: ST a|b|c|aa|bb|cc|aSa|bSb|cSc
或：ST a|b|c|aAa|bAb|cAc, A TS| £ ------------ 06 级陈建伟
错解：ST a|b|c| aSa|bSb|cSc
补充题，对给定RG
S T abA|baB
A T abA|ab
B T baB|ba
构造等价文法，新文法的产生式形如：
ATa, ATaB, A,B € V , a€ T
解：构造得
S T aA'|bB'
A' T bA
B' T aB
A T aA''
A' TbA|ab
B TbB''
B' T aB|ba 06级张力强，岳光同
