内容发布更新时间 : 2024/6/3 20:36:05星期一 下面是文章的全部内容请认真阅读。

第三章 上下文无关语言与下推自动机

a. {w | w至少含有3个1} 0, ???

S→A1A1A1A 1, ??1 A→0A|1A|?

?,1?? ?,1??

b. {w | w以相同的符号开始和结束}

S→0A0|1A1 0,??? A→0A|1A|? 1,??? 0,??0,0?

1,??1,1?

c. {w | w的长度为奇数} 0,???

1,??? 0,???

1,???

?,1?? d.

e.

f.

g.

S→0A|1A A→0B|1B|? B→0A|1A

{w | w的长度为奇数且正中间的符号为0} S→0S0|1S1|0S1|1S0|0 0,??0,0?

1,??1,0?

?,??0,???,$??

{w | w中1比0多} 1,0?S→A1A

0,1?A→0A1|1A0|1A|AA|?

0,??

1,???,1??

?,???,1??,$??

{w | w=wR}

S→0S0|1S1|1|0 0,??0,0?

1,??1,1?

1,??

?,??0,???,$?? ?,??? 空集 S→S

3.6 给出产生下述语言的上下文无关文法： a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。 S→bSaSaS|aSbSaS|aSaSbS|?

b．语言{anbn|n?0}的补集。见问题3.25中的CFG: S→aSb|bY|Ta T→aT|bT|?

c．{w#x | w, x?{0,1}*且wR是x的子串}。 S→UV

U→0U0|1U1|W W→W1|W0|# V→0V|1V|?

d．{x1#x2#?#xk|k?1, 每一个xi?{a,b}* , 且存在i和j使得xi＝xjR}。 S→UVW U→A|?

A→aA|bA|#A|# V→aVa|bVb|#B|# B→aB|bB|#B|# W→B|?

3.14

解：添加新起始变元S0, 去掉B??

S0?A S0?A A?BAB|B|? A?BAB|AB|BA|B|? B?00|? B?00

去掉A??, 去掉A?B S0?A S0?A A?BAB|AB|BA|B|BB A?BAB|AB|BA|00|BB B?00 B?00

去掉S0?A, 添加新变元 S0?BAB|AB|BA|00|BB S0?VB|AB|BA|UU|BB A?BAB|AB|BA|00|BB A?VB|AB|BA|UU|BB B?00 B?UU V?BA U?0

3.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。

a. A?B

方法一：CFG。设有CFG G1＝(Q1,?,R1,S1)和G2=(Q2,?,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,?,R,S0)，其中