計算機理論導引實驗

HUNANUNIVERSITY

Jfnjt1_|T~~tlh計算理論導引實驗報告.TljfjCy匕??七、1■，』、，■題目：A?！钡目膳卸ㄐ訢FA學生姓名：安佳瑋學生學號：20090810101專業(yè)班級：計算機科學與技術1班上課老師：吳昊實驗日期：2011-12-22目錄一、實驗目的2二、實驗方法錯誤！未定義書簽。三、實驗代碼錯誤！未定義書簽。四、測試數(shù)據(jù)以及運行結果6一、實驗目的?ADFA={<B,w>IB是DFA,w是串，B接收w}-證明：Adfa是可判定的。二、試驗方法編寫一個算法/程序，對于給定的輸入<B,w>，可以判定Adfa三、實驗代碼#include<iostream.h>classDFA{public:intnum_Q;//狀態(tài)的個數(shù)int*acc_Q;//接受狀態(tài)集合intstart_Q;//起始狀態(tài)intnum_E;//字母表的個數(shù)int**next_Q;//轉移函數(shù)boolGo(int*w);//接受輸入時的運行結果DFA();//構造函數(shù)?DFA();//析構函數(shù)};DFA::DFA(){intnum_acc;//接受狀態(tài)的總個數(shù)coutvv"狀態(tài)總個數(shù)：";cin>>num_Q;coutvv"字母表總個數(shù)：”；cin>>num_E;coutvv"起始狀態(tài)編號(從0開始)：”cin>>start_Q;coutvv"接受狀態(tài)的總個數(shù):cin>>num_acc;//給接受狀態(tài)數(shù)組動態(tài)分配空間acc_Q=newint[num_acc+1];cout<<"接受狀態(tài)編號(以空格隔開)：”；for(inti=0;i<num_acc;i++){cin>>acc_Q[i];}//標記結尾acc_Q[num_acc]=-1;//轉移函數(shù)數(shù)組分配空間next_Q=newint*[num_Q];for(i=0;i<num_Q;i++){next_Q[i]=newint[num_E];}cout<<"轉移函數(shù)："<<endl;for(intj=0;j<num_Q;j++){for(intk=0;k<num_E;k++){cout<<'編號為"vvjvv”的狀態(tài)接受到編號為"vvkvv”的輸入時，轉移到狀態(tài):”;cin>>next_Q[j][k];}}}//析構函數(shù)DFA::?DFA(){if(acc_Q)deleteacc_Q;if(next_Q)deletenext_Q;}//在輸入w下運行自動機boolDFA::Go(int*w){boolresult;//運行結果int*p=w;//動態(tài)之爭intnow_Q;//當前狀態(tài)now_Q=start_Q;//在輸入下依次尋找下一個狀態(tài)while(*p!=-1){cout<<”當前狀態(tài)"<<now_Q<<"在輸入”<<*p<<”下，轉移到：”；now_Q=next_Q[now_Q][*p];cout<<now_Q<<endl;p++；}p=acc_Q;result=false;//判斷運行完成之后當前狀態(tài)是否在接受狀態(tài)中while(*p!=-1){if(*p==now_Q)result=true;p++;}returnresult;}intmain(){DFAB;int*w;intlen_w;boolgoon=true;while(goon){coutvvendlvv"開始驗證"<<endl;cout<<"輸入字符串長度為：";cin>>len_w;w=newint[len_w+1];cout<<"輸入串中字母的編號依次分別為(以空格隔開)：”；for(inti=0;i<len_w;i++){cin>>w[i];}w[len_w]=-1;cout<<"正在運行中..."vvendl;boolresult=B.Go(w);coutvv"運行結果為:"vvendl;if(result)coutvv"接受"vvendl;elsecout<<"拒絕"<<endl;cout<<"驗證其它字符串？(Y/N)”;charc;cin>>c;if(c=='N')return0;}deletew;}改程序在VC++下可以通過編譯，并且運行結果正確四、測試數(shù)據(jù)以及運行結果以教材上面的一個自動機為例。該自動機識別含有001作為字串的所有字符串，而拒絕其它的串。運行結果如下所示：Ld'文檔\計算理論導引實騷'實^A\Debug\ADFA.eze10202333)開口|po|po|po|po|po|po|po|pA口一禮.fi.fi.fi.fi.fi.fi.fi.fiaz含/|--|/|--|/|--|/|--|/|--|/|--|/I--I.開1格屈丸空gAAAAAAA又-:橫以—In4既.如心日態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)參--■■■4--I;日4--I?:勺.勺.勺.勺.勺.勺.勺.勺?士總態(tài)態(tài)態(tài)數(shù)啪竄寥寥招莒函為為為為為為為為態(tài)沔急又曾苕苕苕苕苕苕苕石1A1A1A1A1A1A1A1A勺：.勺：.勺：.勺：.勺：.勺：.勺：.勺：.1,-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--01010101為為為為為為為為口|po|po|po|po|po|po|po|p扁扁扁扁扁扁扁扁百/|--|/|--|/|--|/|--|/|--|/|--|/|--|.gAAAAAAA又褫接接轉轉接接接一--l.j--l.j--l.j--l.j--l.j--l.j--l.j--I..態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài):10101（以空格隔開）（以空格隔開）0101001233kmkmkm—101011A1A1A1A1A

在在在在在加Utr.u-T月0010符中行態(tài)態(tài)態(tài)態(tài)態(tài)果廣雷運狀狀狀狀狀結入入在既既既B證鬻正當當當當當運拒驗5涂tm--rr*r~r....-*-」」■■100101A1A1A1A1A

在在在在在加Utr.u-T月0012符中行態(tài)態(tài)態(tài)態(tài)態(tài)果廣雷運狀狀狀狀狀結■A.A.仕前.前.前.前.前」."證蕾正當當當當當運接驗PF.O■■■■I.!t串y符ke字y它an其HUNANUNIVERSITYj\VJr\jJ計算理論導引實驗報告yr■■■,&tx.^TFX^F'題目：CFG是P成員學生姓名：安佳瑋學生學號：20090810101專業(yè)班級：計算機科學與技術1班上課老師：吳昊實驗日期：2011-12-22目錄一、實驗目的2二、實驗方法錯誤！未定義書簽。三、實驗代碼錯誤！未定義書簽。四、測試數(shù)據(jù)以及運行結果10上下文無關文法CFGG是否派生某個串W。采用動態(tài)規(guī)劃(DynamicProgramming)設計個多項式時間的驗證算法二、試驗方法編寫一個算法/程序，對于給定的輸入<Gw>，可以在多項式時間內判定ACFG-。三、實驗代碼#include<iostream.h>//第一類規(guī)則，即規(guī)則右邊只含有兩個變元classRegular_1{public:intleft;intright_1;intright_2;};//第二類規(guī)則，即規(guī)則右邊只含有一個終結符或者空classRegular_2{public:intleft;intright;};//表格類，用來存放中間數(shù)據(jù)classTable{public:intsize;//表格的行和列的數(shù)量，與輸入長度相同intnum_v;//表格中每個單元格最多含有的數(shù)量大小，與cfg的變元數(shù)量相同int***value;//用來存放數(shù)據(jù)的三元數(shù)組Table(intnum_v,intnum_w);//構造函數(shù)，參數(shù)指定輸入字符串的長度以及cfg變元的數(shù)量?Table();//析構函數(shù)voidSetValue(inti,intj,intnum);//向表格第i行j列追加數(shù)據(jù)numboolCheckValue(inti,intj,intnum);//檢查表格第i行j列是否含有數(shù)據(jù)num，含有則返回true，否則返回falsevoidPrint();//打印表格的內容};Table::?Table(){if(value)deletevalue;}voidTable::SetValue(inti,intj,intnum){int*p=value[i][j];//尋找追加數(shù)據(jù)的位置while((*p)!=-1){p++；}*p=num;}boolTable::CheckVilue(inti,intj,intnum){int*p=value[i][j];while((*p)!=-1){if((*p)==num)returntrue;p++;}returnfalse;}Table::Table(intnum_v,intnum_w){size=num_w;this->num_v=num_v;value=newint**[num_w];//給value動態(tài)分配，并將初值設為-1for(inti=0;i<num_w;i++){value[i]=newint*[num_w];for(intj=0;j<num_w;j++){value[i][j]=newint[num_v];for(intk=0;k<num_v;k++){value[i][j][k]=-1;}}}}voidTable::Print(){inti,j,k;cout<<"打印表格內容"<<endl;if(size==0){cout<<"表格為空"<<endl;return;}cout<<"表格內容如下:"<<endl;for(i=0;i<size;i++){for(j=0;j<size;j++){cout<<"table["<<i<<"]["<<j<<"]:";for(k=0;k<num_v;k++){if(this->value[i][j][k]==-1)break;elsecout<<this->value[i][j][k]<<"";}cout<<endl;}}}classCFG{public:intnum_v;intnum_e;Regular_1*r1;Regular_2*r2;intstart_v;boolGo(int*w);CFG();?CFG();};CFG::CFG（）{cout<<endl<<"CFG構造函數(shù)"<<endl;intnum_r1,num_r2;inti,j,k;cout<<""<<endl<<"變元總數(shù)：”；cin>>num_v;cout<<”終結符總數(shù):”；cin>>num_e;cout<<""<<endl<<”第一類規(guī)則總數(shù)（規(guī)則右邊為變元）：”cin>>num_r1;r1=newRegular_1[num_r1+1];cout<<""<<endl;cout<<”在下面的輸入中注意：變元編號以及終結符編號從0開始”<<endl;cout<<""<<endl;for（i=0;i<num_r1;i++）{cout<<"第"<<i<<”條規(guī)則的三個變元的編號依次為（以空格隔開）：”；cin>>r1[i].left>>r1[i].right_1>>r1[i].right_2;}r1[i].left=-1;cout<<""<<endl<<”第二類規(guī)則總數(shù)（規(guī)則右邊為終結符或空）：”；cin>>num_r2;r2=newRegular_2[num_r2+1];for（i=0;i<num_r2;i++）{cout<<”第"<<i<<”條規(guī)則的變元的編號和終結符編號（空以-1表示）依次為（以空格隔開）:cin>>r2[i].left>>r2[i].right;}r2[i].left=-1;cout<<""<<endl<<”起始變元的編號為:”；cin>>start_v;}CFG::~CFG（）{if(r1)deleter1;if(r2)deleter2;}boolCFG::Go(int*w){boolresult=false;Regular_1*p1=r1;Regular_2*p2=r2;intlen_w=0;int*p=w;//獲取輸入長度while(*p!=-1){len_w++;p++;}p=w;Tablet(num_v,len_w);inti,j,k,l;cout<<"開始運彳亍"<<endl;if(w[0]==-1){cout<<""<<endl;cout<<"檢查發(fā)現(xiàn)輸入為空...”<<endl;while((*p2).left!=-1){if((*p2).left==start_v&&(*p2).right==-1){cout<<"檢查到起始變元到空的規(guī)則...”<<endl;cout<<"運行完畢！結果為：接受!”<<endl;cout<<""<<endl;result=true;returnresult;}p2++;}cout<<"未發(fā)現(xiàn)從起始變元到空的派生。"<<endl;cout<<”運行完畢，結果為：拒絕”<<endl;cout<<""<<endl;returnfalse;}p2=r2;i=0;cout<<""<<endl;cout<<”開始從頭到尾掃描，將某些變元放入對應的對角線上的表格中："<<endl;while(*p!=-1){while((*p2).left!=-1){if((*p2).right==*p){cout<<"由于變元”<<(*p2).left<<，，派生"<<"終結符”<<*p<<”,故將其放入表格的"<<i<<”行"<<i<<"列”<<endl;t.SetValue(i,i,(*p2).left);}p2++;}p2=r2;p++;i++;}p=w;cout<<""<<endl;cout<<”開始依次向表格的某些單元格添加數(shù)據(jù)..."<<endl;for(l=2;l<=len_w;l++){for(i=0;i<len_w-l+1;i++){j=i+l-1;for(k=i;k<=j-1;k++){while((*p1).left!=-1){if(t.CheckValue(i,k,(*p1).right_1)&&t.CheckValue(k+1,j,(*p1).right_2)){cout<<”table(”<<i<<”,”<<k<<”)中含有變元”<<(*p1).right_1<<”而且table("<<k+1<<","<<j<<")中含有"<<(*p1).right_2;cout<<”,因此將變元”<<(*p1).left<<”放入table(”<<i<<”,”<<j<<”)中”<<endl;t.SetValue(i,j,(*p1).left);p1++;p1=r1;}}t.Print();if(t.CheckValue(1,len_w-1,start_v)){cout<<"起始變元"<<start_v<<"在talbe(0,"<<len_w-1<<”)中"<<endl;cout<<"運行完畢！結果為：接受!”<<endl;cout<<""<<endl;returntrue;}else{cout<<"起始變元"<<start_v<<"在不在talbe(0,"<<len_w-1<<”)中”<<endl;cout<<”運行完畢！結果為：拒絕!”<<endl;cout<<""<<endl;returnfalse;}}main(){cout<<"CFG是P成員判定程序"<<endl;CFGc;while(true){int*w;intlen_w;cout<<""<<endl<<”輸入w的長度：";cin>>len_w;w=newint[len_w+1];if(len_w==0)cout<<""<<endl;elsecout<<"依次輸入w的內容的編號(以空格隔開):";for(inti=0;i<len_w;i++){cin>>w[i];}w[i]=-1;c.Go(w);cout<<"驗證其它字符串？(Y/N)”;charc;cin>>c;if(c=='N')return;}改程序在VC++下可以通過編譯，并且運行結果正確四、測試數(shù)據(jù)以及運行結果以教材習題上面的一個CFG為例。該CFG描述如下：S->RTR->TRIaT->TRIb在該CFG下面測試輸入w1=baba和w2=ababb測試結果如下:F:\文檔'計算理論導引實驗'實驗B'Debu叭CFG_P-ezeCFG是P成員判定程序CFG構造函數(shù)第一類規(guī)則總數(shù)（規(guī)則右邊為變元）：3在下面的輸入中注意：變元編號以及終結符編號從。開始>>>

開開開

鬲鬲鬲

空空空

以以以

c--c--c-

為為為

次次次

□Ipolpolp

扁扁扁

L4■tl1山■l--I.L^^--I?

元元元

變變變

個個個

三三三

的的的

■■■■■■■■■

貝貝貝

規(guī)規(guī)規(guī)

012騷耕"5示1秦規(guī)則的變元的編導和終結特編導（空以T表示次為《以空

次為《以空圈開n10隔開〉：21起始變元的編號為汩WI闿.4所御容的編號（以空格隔開）=1010一開始運行卜、士口士口士口士口++田￡七-￡.M?M-pr^kr.G-vkr.G-vrn4-.七-4---I.2:■■-4-■二-PTrfalfclfalfalufcLX.」.3H.S一悔.一眠皈版皈手?弟qKl1頭元元元元從變變變變始于于于于開由由由由尋1010

fin應的對角線上的表格中:備的0行盼|■的:L抒:L歹！旨的2泓歹!備的3行3列理始依次向表格的某些單元掐添加數(shù)據(jù)…table<8,0>J=冒卜1”0,0）1:二含有變元2而且table<l,l>Lble<l,l>l==f§#變元1而且table<2,2>國隊《2,2）匚二含宥變元2而且table<3,3>^able<2,2>l==r含有變&而且table<3,3>^able<0,l>l==r§;<^^lift-&table<2,2>3耕1應1」〉1=二吾肴變元1而且table<2,3>ZfiihlE弱，1〉巾含有變元1而且teihlE《2J〉^able<0,l>l==r^^'^^2ifij-&table<2,3>4卜1已弱,1〉中香有變元2而且table<2,3>R———二一馬丁印表格內容有變元2而且table<l,l>1121122211

有有有有有有有有有有

含含含含含含含含含含L---lL-~uL---lL-~-IL-UL-IL-uL-~u■-uL-u業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)1201200012

元元元元元元元元元元

變變變變變變變變變變入入入入入入入入入入table<0table<0tabledtable<2table<2table<0tabledtable<0table<0table<0口口呂口口口口口口辰格內容如下二k;able[0][0]：2kable[0Hl]：l2Ldg?F:\文檔'計算理論導引實驗'實驗B'Debu叭CFG_P-eze起始變元的編號為汩容的編號（以空格隔開）=1010寵運行成結結結結-pv^tr-s-G-yG-s-G-v.、3,i-.2:■■-￡.2:■■-的生生生生割、^^^1/頭元元元元從變變變變始于于于于開由由由由邕故，符嘰故二瓶'嵌符虬故二表表表表

入入入入應的對角線上的表格中:旨的?行矽、|■的1行1歹！3的2行2歹!備的3行3列醫(yī)始依次向表格的某些單元格添加數(shù)據(jù)…table<0,0>J…一國hie皿巾含有變元2而且ghlE《l,l）l==r吾肴變元1而且table<2,2>^able<2,2>l==r含有變元2而且table<3,3>ghlE《2,2）l:二吾首變元2而且table<3,3>^able<0,l>l==r^^'^^；lifij-&table<2,2>變元1而且table<2,3>上211隊0,1〉1=二含有變元1而且1；511）1￡《2,3〉k^hlE弱，1〉□吾有變元2而且tmhlE<2-3〉」〉巾含’、有變元2而且table<l,l>h;able<0辰格內容如下二k:able[0H0]^able[0][l]^able[0H2]^able[0][3]^able[l][0]table^able[l][2]tabled][3]^able[2][0]^able[2Hl]^able[2][2]國hie⑵[3]^able[3][0]^able[3Hl]table[3][2]^able[3J[3]恒始變元回在talbe<0,3>中愜行完畢！結果為：接受，2100變元2而且table<2,3>丁印表格內容險證其它字符串？（必）y1121122211

有有有有有有有有有有

含含含含含含含含含含此此此此此此此此此此1201200012

元元元元元元元元元元

變變變變變變變變變變入入入入入入入入入入table<0table<0table<ltable<2table<2table<0table<ltable<0table<0table<0口口口呂口口口口口g‘F:、文檔'計算理論導引實驗'實驗B'Debu叭CFG_P-eze容的編號（以空格隔開）=01011寵運行，士口士口士口士口士口44田。2.M..2--..2--?M-pv^k4kr.、kr.G-<btm￡.2:■■-,i-.2:■■-4-■二招生生生生生厚質質質氐暇512122頭元元元元元從變變變變變始于于于于于開由由由由由表表表表表

入入入入入應的對角線上的表格中:目的昉蜘|■的1行1歹！備的2畝歹!3的3色歹！備的4行4歹！肝始依次向表格的某些單元掐添加數(shù)據(jù)…table<8,0>J=^able<l,l>l==r^^'^^2ijTlKtable<2,2>冒hlet:L,:L）巾含肴變元2而且七耕1應2,2）ghlE《2,2）l:二吾首變元1而且table<3,3>國hie皿巾含有變元:!.而且^ab