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

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

1、第3章、上下文無關(guān)語言習(xí)題解答-練習(xí)3.1回憶一下例3.3中給出的CFGG4。為方便起見，用一個字母重新命名它的變元如下：E→E＋T

2、TT→T×E

3、FF→（E）

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

5、m,n30}和B={anbncm

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

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

8、下不封閉。證明：a.先說明A,B均為上下文無關(guān)文法，對A構(gòu)造CFGC1S?aS

9、T

10、eT?bTc

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

12、R

13、eR?aRb

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

15、n30}（假設(shè)m≤n）不是上下文無關(guān)語言，所以上下文無關(guān)語言在交的運算下不封閉。9b.用反證法。假設(shè)CFL在補運算下封閉，則對于(a)中上下文無關(guān)語言A,B，,也為CFL。因為CFL對并運算封閉，所以也為CFL，進而知道為CFL。由DeMorgan定律，得出是CFL。這與(a)

16、的結(jié)論矛盾，所以CFL對補運算不封閉。3.3設(shè)上下文無關(guān)文法G：R→XRX

17、SS→aTb

18、bTaT→XTX

19、X

20、εX→a

21、b回答下述問題：a.G的變元和終結(jié)符是什么？起始變元是哪個？答：變元是：R，X，S，T；起始變元是R。終結(jié)符是：a，b，εb.給出L(G)中的三個字符串。答：ab，ba，aab。c.給出不在L(G)中的三個字符串。答：a，b，ε。d.是真是假：。答：假e.是真是假：。答：真f.是真是假：。答：假g.是真是假：。答：假h.是真是假：。答：真i.是真是假：。答：假j.是真是假：。答：真k.是真是假：。答：真l

22、.是真是假：。答：假m.用普通的語言描述L(G)：93.4和3.5給出產(chǎn)生下述語言的上下文無關(guān)文法和PDA，其中字母表S={0,1}。a.{w

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

24、1A

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

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

27、

28、1A1A→0A

29、1A

30、e讀輸入中的第一個符號并將其推入棧。繼續(xù)讀后面的符號，同時非確定性地猜想輸入符號和棧符號是否相同，如果相同則轉(zhuǎn)移到接受狀態(tài)，如果此時輸入結(jié)束，則接受這個輸入，否則繼續(xù)輸入。0,e?e1,e?e1,1?e0,0?e0,e?01,e?1c.{w

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

32、0

33、1A→0

34、1讀輸入中的1個符號，轉(zhuǎn)移到接受狀態(tài)，再讀一個符號，轉(zhuǎn)移到非接受狀態(tài)，如此循環(huán)。可見接受長度為奇數(shù)的字符串。0,e?e1,e?e0,e?e1,e?ed.{w

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

36、09A→0

37、1讀輸入

38、中的1個符號，推入1個0。每當(dāng)讀到0時就非確定性地猜想已經(jīng)到達字符串的中點，然后變成讀輸入中的1個符號，就把棧中的0彈出。當(dāng)輸入結(jié)束的同時棧被排空，則接受，否則拒絕。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個的所有字符串。//T1S可以產(chǎn)生1比0多2個以上的所有字符串。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如果輸入

43、0時，棧頂元素是1，則彈出1；否則將0推入堆棧。如果輸入1時，棧頂元素是0，則彈出0；否則將1推入堆棧。非確定地猜想棧頂元素是1，且棧中都是1，如果是，則接受；否則拒絕。c.{w

44、w=wR，即w是一個回文，回文是順讀和倒讀都一樣的字符串}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是回文，那么它的中點有三種可能：1)字符個數(shù)是奇數(shù)，中點的字符是1。2)字符個數(shù)是奇數(shù)，中點的字符是0。3)字符個數(shù)是偶數(shù)，中點的字符是e。9開始時，把讀到的字符推入

49、棧中，在每一步非確定性地猜想已經(jīng)到達字符串的中點。然后變成把讀到的每一個字符彈出棧，檢查在輸入中和在棧頂讀到的字符是否一樣。如果它們總是一樣的，并且當(dāng)輸入結(jié)束時棧是空的，則接受；否則拒絕。b.空集S→S3.6給出產(chǎn)生下述語言的上下文無關(guān)文法：a．字母表{a,b}上a的個數(shù)是b的個數(shù)的兩倍的