3上下文无关语言练习文档格式.doc

3上下文无关语言练习文档格式.doc

《3上下文无关语言练习文档格式.doc》由会员分享，可在线阅读，更多相关《3上下文无关语言练习文档格式.doc（9页珍藏版）》请在冰点文库上搜索。

aRb |e //生成anbn

由此知A,B均为上下文无关语言。

由例3.20,A∩B={anbncn|n³

0}（假设m≤n）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。

b.用反证法。

假设CFL在补运算下封闭，则对于（a）中上下文无关语言A,B，,也为CFL。

因为CFL对并运算封闭，所以也为CFL，进而知道为CFL。

由DeMorgan定律，得出是CFL。

这与（a）的结论矛盾，所以CFL对补运算不封闭。

3.3设上下文无关文法G：

R→XRX|S

S→aTb|bTa

T→XTX|X|ε

X→a|b

回答下述问题：

a.G的变元和终结符是什么？

起始变元是哪个？

变元是：

R，X，S，T；

起始变元是R。

终结符是：

a，b，ε

b.给出L（G）中的三个字符串。

ab，ba，aab。

c.给出不在L（G）中的三个字符串。

a，b，ε。

d.是真是假：

。

假

e.是真是假：

真

f.是真是假：

g.是真是假：

h.是真是假：

i.是真是假：

j.是真是假：

k.是真是假：

l.是真是假：

m.用普通的语言描述L（G）：

3.4和3.5给出产生下述语言的上下文无关文法和PDA，其中字母表S={0,1}。

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

S→A1A1A1A

A→0A|1A|e

读输入中的符号。

每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。

同时非确定性地转移，并把1个1弹出栈。

如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。

否则拒绝这个输入。

e,1®

e

1,e®

1

0,e®

e

b.{w|w以相同的符号开始和结束，w的长大于1}

S→0A0|1A1

读输入中的第一个符号并将其推入栈。

继续读后面的符号，同时非确定性地猜想输入符号和栈符号是否相同，如果相同则转移到接受状态，如果此时输入结束，则接受这个输入，否则继续输入。

0,e®

1,e®

1,1®

0,0®

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

S→ASA|0|1

A→0|1

读输入中的1个符号，转移到接受状态，再读一个符号，转移到非接受状态，如此循环。

可见接受长度为奇数的字符串。

d.{w|w的长度为奇数且正中间的符号为0}

S→ASA|0

读输入中的1个符号，推入1个0。

每当读到0时就非确定性地猜想已经到达字符串的中点，然后变成读输入中的1个符号，就把栈中的0弹出。

当输入结束的同时栈被排空，则接受，否则拒绝。

1,0®

e,e®

$

e,$®

e.{w|w中1比0多}

S→T1T| T1S //T1T可以产生1比0多1个的所有字符串。

//T1S可以产生1比0多2个以上的所有字符串。

T→0T1T|1T0T|ε //T可以产生0和1数目相等的所有字符串。

0,1®

如果输入0时，栈顶元素是1，则弹出1；

否则将0推入堆栈。

如果输入1时，栈顶元素是0，则弹出0；

否则将1推入堆栈。

非确定地猜想栈顶元素是1，且栈中都是1，如果是，则接受；

否则拒绝。

f.{w|w=wR，即w是一个回文，回文是顺读和倒读都一样的字符串}

S→0S0|1S1|1|0|ε

如果W是回文，那么它的中点有三种可能：

1）字符个数是奇数，中点的字符是1。

2）字符个数是奇数，中点的字符是0。

3）字符个数是偶数，中点的字符是e。

开始时，把读到的字符推入栈中，在每一步非确定性地猜想已经到达字符串的中点。

然后变成把读到的每一个字符弹出栈，检查在输入中和在栈顶读到的字符是否一样。

如果它们总是一样的，并且当输入结束时栈是空的，则接受；

g.空集

S→S

3.6给出产生下述语言的上下文无关文法：

a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。

S→bSaSaS|aSbSaS|aSaSbS|e

b．语言{anbn|n³

0}的补集。

见问题3.25中的CFG:

分析问题：

{anbn|n³

0}语言的CFG为：

S→aSb|e。

违反条件的情况可能有两种：

1.一种是在连续的a中间插入了字符b，或者在连续的b中间插入了字符a。

2.a和b的数目不相等。

所以可以设计文法如下：

S→aSb|bT|Ta //只能生成错序的或者a和b个数不相等的字符串。

T→aT|bT|e //生成所有由a,b组成的字符串。

c．{w#x|w,xÎ

{0,1}*且wR是x的子串}。

分析问题：

根据题义，语言w#x可以分解成为：

其中T是所有由0,1组成的字符串。

S→UT

U→0U0|1U1|#T //生成w#TwR

T→0T|1T|e //生成所有由0，1组成的字符串

d．{x1#x2#¼

#xk|k³

1,每一个xiÎ

{a,b}*,且存在i和j使得xi＝xjR}。

根据题义，语言x1#x2#¼

#xk可以分解成为：

S→UVW

U→A#U|e

W→#AW|e

A→aA|bA|e //生成所有由a，b组成的字符串xi

V→aVa|bVb|#U

3.7略。

3.8证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同意思。

G2如下：

＜句子＞→＜名词短语＞＜动词短语＞

＜名词短语＞→＜复合名词＞|＜复合名词＞＜介词短语＞

＜动词短语＞→＜复合动词＞|＜复合动词＞＜介词短语＞

＜介词短语＞→＜介词＞＜复合名词＞

＜复合名词＞→＜冠词＞＜名词＞

＜复合动词＞→＜动词＞|＜动词＞＜名词短语＞

＜冠词＞→a_|the_

＜名词＞→boy_|girl_|flower_

＜动词＞→touch_|1ikes_|Sees_

＜介词＞→with_

答：

1.第一种最左派生

<

句子>

Þ

名词短语>

动词短语>

复合名词>

冠词>

名词>

a_<

a_girl_<

复合动词>

动词>

a_girl_touches_<

a_girl_touches_<

介词短语>

a_girl_touches_the_<

介词名词>

a_girl_touches_the_boy_<

介词>

a_girl_touches_the_boy_with_<

a_girl_touches_the_boy_with_the_<

a_girl_touches_the_boy_with_the_flower

含义是：

女孩碰这个带着花的男孩

2.第二种最左派生

含义是：

女孩用花碰这个男孩

3.9给出产生语言A={aibjck|i,j,k³

0且或者i=j或者j=k}的上下文无关文法。

你给出的文法是歧义的吗？

为什么？

解：

下面是产生A的一个CFG:

UV|AB

U®

aUb|e //产生aibj，i=j

V®

cV|e //产生ck

A®

aA|e //产生ai

B®

bBc|e //产生bjck，j=k

这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：

SÞ

UVÞ

aUbVÞ

abVÞ

abcVÞ

abc

ABÞ

aABÞ

aBÞ

abBcÞ

3.10给出识别3.9中语言A的下推自动机的非形式描述。

其非形式描述为：

此PDA有两个非确定性的分支：

1.读输入中的符号a，把一个a推入栈。

同时非确定性地读b，每读一个b从栈中弹出一个a，若栈中没有a则拒绝。

当栈为空时进入接受状态。

继续读输入符号，每读一个c，不改变栈内容和状态，若读入a或b则拒绝。

2.读输入中的符号a，不改变栈内容。

当读到b时，将一个b推入栈，同时非确定性地读c，每读一个c从栈中弹出一个b，若栈中没有b则拒绝。

如果输入串结束时，一个非确定性分支在接受状态则接受，否则拒绝。

3.13设有上下文无关文法G:

TT|U

0T|T0|#

0U00|#

a.用普通的语言描述L（G）。

b.证明L（G）不是正则的。

TT|U

0T|T0|# //产生所有由0和一个#组成的字符串

0U00|# //产生由0和#组成的字符串，且符号#右边的0的个数是左

边的0的个数的二倍。

a.L（G）={0i#0j#0k|i,j,k³

0}∪{0i#02i|i³

1}。

c.假设是正则的。

令p是泵引理给出的泵长度，取s为字符串0p#02p。

由于s是L（G）的一个成员且长度大于p，泵引理保证s可以分成3段s=xyz,使得对于任意的i³

0，xyiz在L（G）中。

根据泵引理的条件3：

|xy|£

p，则y一定只由0组成，从而字符串xyyx=0p+1#02p，所以xyyxÏ

L（G）。

矛盾，故L（G）不是正则的。

3.14用定理3.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。

BAB|B|e

00|e

1）添加新起始变元S0,

S0®

A

2）删除e规则B®

BAB|AB|BA|A|B|e

00

3）删除e规则A®

e,

A|e //乔姆斯基范式文法允许规则S®

e

BAB|AB|BA|B|BB

4）删除单一规则A®

B

A|e

A®

BAB|AB|BA|00|BB

B®

5）删除单一规则S0®

A,

BAB|AB|BA|00|BB|e

BAB|AB|BA|00|BB

00

6）添加新的变元和规则

S0®

VB|AB|BA|UU|BB|e

VB|AB|BA|UU|BB

UU

BA

3.19证明：

设G是一个Chomsky范式CFG，则对任一长度n≥1的字符串wÎ

L（G）,w的任何派生恰好有2n-1步。

对字符串长度n使用数学归纳法。

归纳基础：

当n=1时，对于Chomsky范式CFG，长度为1的字符串必由1步派生，此时命题为真。

归纳步骤：

假设命题对长度不超过k≥1的字符串成立，要证明命题对长度为k+1的字符串成立。

对于长度为k+1的字符串s=s1s2¼

sk+1，存在S0的一个直接派生S0Þ

AB，使得A产生子串s1s2¼

sp，B产生子串sp+1sp+2¼

sk+1，其中1≤p≤k+1。

由归纳假设，A产生子串s1s2¼

sp需要2p-1步派生，而B产生子串sp+1sp+2¼

sk+1需要2（k+1-p）-1步派生。

因此，S0产生字符串s需要1+（2p-1）+[2（k+1-p）-1]＝2k+1＝2（k+1）-1步派生。

即当n=k+1时命题亦真。

证毕。

9