3、上下文無(wú)關(guān)語(yǔ)言練習(xí)

《3、上下文無(wú)關(guān)語(yǔ)言練習(xí)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第3章、上下文無(wú)關(guān)語(yǔ)言習(xí)題解答-練習(xí)3.1回憶一下例3.3中給出的CFGG4。為方便起見，用一個(gè)字母重新命名它的變?cè)缦拢篍→E＋T

2、TT→T×E

3、FF→（E）

4、a給出下述字符串的語(yǔ)法分析樹和派生。a.ab.a+ac.a+a+ad.((a))答：a.b.c.d.3.2a.利用語(yǔ)言A={ambncn

5、m,n30}和B={anbncm

6、m,n30}以及例3.20(語(yǔ)言B={anbncn

7、n30}不是上下文無(wú)關(guān)的)，證明上下文無(wú)關(guān)語(yǔ)言在交的運(yùn)算下不封閉。b.利用(a)和DeMorgan律(定理1.10)，證明上下文無(wú)關(guān)語(yǔ)言在補(bǔ)運(yùn)算下不封閉。證明：a.先說(shuō)明

8、A,B均為上下文無(wú)關(guān)文法，對(duì)A構(gòu)造CFGC1S?aS

9、T

10、eT?bTc

11、e//生成bncn對(duì)B,構(gòu)造CFGC2S?Sc

12、R

13、eR?aRb

14、e//生成anbn由此知A,B均為上下文無(wú)關(guān)語(yǔ)言。由例3.20,A∩B={anbncn

15、n30}（假設(shè)m≤n）不是上下文無(wú)關(guān)語(yǔ)言，所以上下文無(wú)關(guān)語(yǔ)言在交的運(yùn)算下不封閉。9b.用反證法。假設(shè)CFL在補(bǔ)運(yùn)算下封閉，則對(duì)于(a)中上下文無(wú)關(guān)語(yǔ)言A,B，,也為CFL。因?yàn)镃FL對(duì)并運(yùn)算封閉，所以也為CFL，進(jìn)而知道為CFL。由DeMorgan定律，得出是CFL。這與(a)的結(jié)論矛盾，所以CFL對(duì)補(bǔ)運(yùn)算不封閉。3.3設(shè)上下文

16、無(wú)關(guān)文法G：R→XRX

17、SS→aTb

18、bTaT→XTX

19、X

20、εX→a

21、b回答下述問(wèn)題：a.G的變?cè)徒K結(jié)符是什么？起始變?cè)悄膫€(gè)？答：變?cè)牵篟，X，S，T；起始變?cè)荝。終結(jié)符是：a，b，εb.給出L(G)中的三個(gè)字符串。答：ab，ba，aab。c.給出不在L(G)中的三個(gè)字符串。答：a，b，ε。d.是真是假：。答：假e.是真是假：。答：真f.是真是假：。答：假g.是真是假：。答：假h.是真是假：。答：真i.是真是假：。答：假j.是真是假：。答：真k.是真是假：。答：真l.是真是假：。答：假m.用普通的語(yǔ)言描述L(G)：93.4和3.5給出產(chǎn)生下述

22、語(yǔ)言的上下文無(wú)關(guān)文法和PDA，其中字母表S={0,1}。a.{w

23、w至少含有3個(gè)1}S→A1A1A1AA→0A

24、1A

25、e讀輸入中的符號(hào)。每讀一個(gè)1，把一個(gè)1推入棧，每讀1個(gè)0，不讀棧也不寫棧。同時(shí)非確定性地轉(zhuǎn)移，并把1個(gè)1彈出棧。如果能轉(zhuǎn)移三次，共彈出三個(gè)1，則接受這個(gè)輸入，并繼續(xù)讀輸入符號(hào)直至結(jié)束。否則拒絕這個(gè)輸入。e,1?e1,e?10,e?ee,1?ee,1?e1,e?e0,e?eb.{w

26、w以相同的符號(hào)開始和結(jié)束，w的長(zhǎng)大于1}S→0A0

27、1A1A→0A

28、1A

29、e讀輸入中的第一個(gè)符號(hào)并將其推入棧。繼續(xù)讀后面的符號(hào)，同時(shí)非確定性地猜想輸入符號(hào)和

30、棧符號(hào)是否相同，如果相同則轉(zhuǎn)移到接受狀態(tài)，如果此時(shí)輸入結(jié)束，則接受這個(gè)輸入，否則繼續(xù)輸入。0,e?e1,e?e1,1?e0,0?e0,e?01,e?1c.{w

31、w的長(zhǎng)度為奇數(shù)}S→ASA

32、0

33、1A→0

34、1讀輸入中的1個(gè)符號(hào)，轉(zhuǎn)移到接受狀態(tài)，再讀一個(gè)符號(hào)，轉(zhuǎn)移到非接受狀態(tài)，如此循環(huán)?？梢娊邮荛L(zhǎng)度為奇數(shù)的字符串。0,e?e1,e?e0,e?e1,e?ed.{w

35、w的長(zhǎng)度為奇數(shù)且正中間的符號(hào)為0}S→ASA

36、09A→0

37、1讀輸入中的1個(gè)符號(hào)，推入1個(gè)0。每當(dāng)讀到0時(shí)就非確定性地猜想已經(jīng)到達(dá)字符串的中點(diǎn)，然后變成讀輸入中的1個(gè)符號(hào)，就把棧中的0彈出。當(dāng)輸入結(jié)

38、束的同時(shí)棧被排空，則接受，否則拒絕。1,e?00,e?e0,e?01,0?e0,0?ee,e?$e,$?eb.{w

39、w中1比0多}答：S→T1T

40、T1S//T1T可以產(chǎn)生1比0多1個(gè)的所有字符串。//T1S可以產(chǎn)生1比0多2個(gè)以上的所有字符串。T→0T1T

41、1T0T

42、ε//T可以產(chǎn)生0和1數(shù)目相等的所有字符串。1,e?1e,1?e0,e?0e,1?ee,e?$e,$?e1,0?e0,1?e如果輸入0時(shí)，棧頂元素是1，則彈出1；否則將0推入堆棧。如果輸入1時(shí)，棧頂元素是0，則彈出0；否則將1推入堆棧。非確定地猜想棧頂元素是1，且棧中都是1，如果是，則接

43、受；否則拒絕。c.{w

44、w=wR，即w是一個(gè)回文，回文是順讀和倒讀都一樣的字符串}S→0S0

45、1S1

46、1

47、0

48、ε1,e?10,e?e0,e?01,1?e0,0?ee,e?$e,$?e1,e?ee,e?e如果W是回文，那么它的中點(diǎn)有三種可能：1)字符個(gè)數(shù)是奇數(shù)，中點(diǎn)的字符是1。2)字符個(gè)數(shù)是奇數(shù)，中點(diǎn)的字符是0。3)字符個(gè)數(shù)是偶數(shù)，中點(diǎn)的字符是e。9開始時(shí)，把讀到的字符推入棧中，在每一步非確定性地猜想已經(jīng)到達(dá)字符串的中點(diǎn)。然后變成把讀到的每一個(gè)字符彈出棧，檢查在輸入中和在棧頂讀到的字符是否一樣。如果它們總是一樣的，并且當(dāng)輸入結(jié)束時(shí)棧是空的，則接受；否則

49、拒絕。b.空集S→S3.6給出產(chǎn)生下述語(yǔ)言的上下文無(wú)關(guān)文法：a．字母表{a,b}上a的個(gè)數(shù)是b的個(gè)數(shù)的兩倍的