3上下文无关语言练习文档格式.doc
- 文档编号:3947063
- 上传时间:2023-05-02
- 格式:DOC
- 页数:9
- 大小:114KB
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上下文 无关 语言 练习