3-1. 構(gòu)造上下文無關(guān)文法用以產(chǎn)生：
(a) 有相同數(shù)目的0 和1 的所有0, 1 符號串。
(b) {a1a2…anan…a2a1|ai∈{0,1}, 1≤ i ≤n}。

（a）解題思路：L(G) ={},，

P:? ?S->0S1|,? ? ?G={{S},{0,1},P,S}

?

(b)

P:S->0S0|1S1|, G={{S},{0,1},P,S}

3-2. 有以下文法：G = ({S,B,C},{a,b,c},P, S),其中：P:

1)S → aSBC | abC,

2)CB → BC,

3)bB → bb,

4)bC → bc,

5)cC → cc,

求L(G)=?

一步步推導(dǎo)可得L(G) ={},，

?

3-3. 設(shè)文法G 由如下規(guī)則定義：
S → AB A → Aa|bB
B → a|Sb
給出下列句子形式的派生樹:
(1) baabaab (2) bBABb

（1）

?

（2）

3-4. 寫一個程序模擬一個確定性的PDA。

#------------------------------------------------------------------------------- # Name: PDA # Purpose: # # Author: nkenen # # Created: 18/02/2020 # Copyright: (c) postgres 2020 # Licence: <your licence> #------------------------------------------------------------------------------- #構(gòu)造下推自動器PDA #確定性和非確定由規(guī)則確定和非確定來確定 #當(dāng)轉(zhuǎn)移時確定只有一個狀態(tài)為確定性，否則為非確定性 import random#PDA的棧 class Stack(object):def __init__(self):self.list = []def is_empty(self):return self.list == []def push(self,item):self.list.append(item)def pop(self):if self.is_empty():returnelse:return self.list.pop()def top(self):if self.is_empty():returnelse:return self.list[-1]#PDA的跳轉(zhuǎn)規(guī)則，由兩個列表映射 class Rule(object):def __init__(self):self.input3p = []#輸入條件self.output2p = []#輸出規(guī)則def copy(self,other_rule):self.input3p = list(other_rule.input3p)self.output2p = list(other_rule.output2p)def append(self,lsti,lsto):self.input3p.append(lsti)#增加條件self.output2p.append(lsto)#與之對應(yīng)增加輸出規(guī)則def out(self,lst):index = 0index = self.input3p.index(lst)#找到對應(yīng)規(guī)則定位return self.output2p[index]#輸出映射規(guī)則def clear(self):self.input3p.clear()self.output2p.clear()#PDA結(jié)構(gòu) class PDA(object):def __init__(self,Input,sigma,Q,Gamma,Belta,q0,z0,F):self.Input = Inputself.Sigma =sigmaself.Q = Qself.Gamma = Gammaself.rule = Rule()self.rule.copy(Belta)self.stack = Stack()self.q0 = q0self.z0 = z0self.F = Fdef ruleappend(self,qi,ai,zi,qo,zo):self.rule.append(qi,ai,zi,qo,zo)#下一次跳轉(zhuǎn)條件def nextrule(self,lst):#(qo,zo)return self.rule.out(lst)#該函數(shù)為本次PDA的對應(yīng)操作函數(shù)#若為不同的規(guī)則不同的輸入字符串需要修改def PushDownString(self):q = self.q0zi = Nonezo = self.z0for i in range(len(self.Input)+1):if q == 1:if zi == self.stack.top():self.stack.pop()zi = self.stack.top()elif q == 0 and zo != None:self.stack.push(zo)zi = Noneprint(self.Input[i:],q,self.stack.list)if i < len(self.Input):[q,zo] = self.nextrule([q,self.Input[i],zi])else:self.stack.pop()class Lanug(object):def __init__(self,Gamma):self.string = 'c'self.Gamma = Gammadef create(self,len,num):w = ''for _ in range(len):i = random.randint(0,num)w += self.Gamma[i]return w+self.string+w[::-1]#該程序只是模擬一個確定性pda題目的解題步驟 #就是課程ppt上的一個例題，算不算模擬了PDA我也不知道 def main():sigma = ['a','b','c']Q = [0,1]Gamma = {'A','B'}Belta = Rule()q0 = 0z0 = '#'F = {1}L_creater = Lanug(['a','b','c'])Input = L_creater.create(20,1)Belta.append([0,'a',None],[0,'A'])Belta.append([0,'b',None],[0,'B'])Belta.append([0,'c',None],[1,None])Belta.append([1,'a','A'],[1,None])Belta.append([1,'b','B'],[1,None])pda = PDA(Input,sigma,Q,Gamma,Belta,q0,z0,F)pda.PushDownString()passif __name__ == '__main__':main()

3-5. 寫一個程序以正則文法G 作為輸入，構(gòu)造G 相應(yīng)的有限自動機。

#------------------------------------------------------------------------------- # Name: NFA # Purpose: # # Author: nkenen # # Created: 18/02/2020 # Copyright: (c) postgres 2020 # Licence: <your licence> #------------------------------------------------------------------------------- class Reggram(object):def __init__(self,Vn=[],Vt=[],P={},S=None):self.Vn = Vnself.Vt = Vtself.P = Pself.S = S#打印函數(shù)def Print(self):print("正則文法G:")print("VN =",self.Vn)print("VT =",self.Vt)print("P =",self.P)print("S =",self.S)class Delta(object):def __init__(self):self.inputp = []self.outputp = []def copy(self,other_delta):self.inputp = list(other_delta.inputp)self.outputp = list(other_delta.outputp)def append(self,lsti,lsto):self.inputp.append(lsti)self.outputp.append(lsto)#映射的狀態(tài)空間增值def varappend(self,lst,input):index = 0index = self.inputp.index(lst)self.outputp[index].append(input)def out(self,lst):index = 0index = self.inputp.index(lst)return self.outputp[index]def clear(self):self.inputp.clear()self.outputp.clear()def Print(self):for i in range(len(self.inputp)):print("δ",self.inputp[i],"=",self.outputp[i])#注意：DFA與NFA區(qū)別在于轉(zhuǎn)移規(guī)則是否對應(yīng)唯一狀態(tài) #在程序我就直接用的NFA標(biāo)注，感覺DFA就是NFA一種特殊情況 class NFA(object):def __init__(self,Sigma=[],Q=[],delta=Delta(),q0=None,F=[]):self.Sigma = Sigmaself.Q = Qself.delta=deltaself.q0=q0self.F=F#將文法轉(zhuǎn)換成自動機的函數(shù)#根據(jù)轉(zhuǎn)化規(guī)則def gramtonfa(self,G=Reggram()):self.Sigma = list(G.Vt)self.Q = list(G.Vn)self.Q.append('T')self.q0 = 'S'if None in G.P['S']:self.F.append('S')self.F.append('T')else:self.F.append('T')for vn in G.Vn:if len(vn) ==1:for vt in G.Vt:flag = 1self.delta.append([vn,vt],[])for i in G.P[vn]:if i!= None and len(i) == 1:if i[0] == vt:if flag == 1:self.delta.varappend([vn,vt],'T')flag = 0elif i!= None and len(i) > 1:if i[0] == vt:if i[1] in G.Vn:self.delta.varappend([vn,vt],i[1])for vt in G.Vt:self.delta.append(['T',vt],[])def Print(self):print("正則文法G相應(yīng)的有限自動機M：")print("∑ =",self.Sigma)print("Q =",self.Q)self.delta.Print()print("q0 =",self.q0)print("F =",self.F)def main():#第三張ppt的正則轉(zhuǎn)化例題G = Reggram(['S','B'],['a','b'],{'S':['aB'],'B':['bS','aB','a']},'S')G.Print()M = NFA()M.gramtonfa(G)M.Print()passif __name__ == '__main__':main()

?

總結(jié)

以上是生活随笔為你收集整理的宗成庆《自然语言理解》第三章作业的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。