將正規(guī)式R化成最小DFA的狀態(tài)圖

實(shí)驗(yàn)一：詞法分析器的設(shè)計(jì)一、實(shí)驗(yàn)?zāi)康模骸?〕掌握詞法分析器的構(gòu)造過(guò)程以及根本方法。〔2〕理解正規(guī)式、NFA、DFA及最小化DFA的轉(zhuǎn)換過(guò)程和方法。二、實(shí)驗(yàn)內(nèi)容給定一個(gè)正規(guī)式R=XY*|YX*Y|XYX，請(qǐng)先在練習(xí)本上將此正規(guī)式轉(zhuǎn)變?yōu)镹FA、DFA、最小化DFA；對(duì)你所完成的最小化DFA進(jìn)行編程，完成詞法分析器工作。三.設(shè)計(jì)分析1.將給定的正規(guī)式R=>NFA；2.將NFA=>DFA;3.將DFA=>最小DFA;4，按照最小DFA的狀態(tài)圖，編寫(xiě)相應(yīng)的程序。將正規(guī)式R=XY*|YX*Y|XYX化成最小DFA的狀態(tài)圖如下：圖1-1最小DFA狀態(tài)圖簡(jiǎn)要方法：根據(jù)最小DFA的狀態(tài)圖設(shè)計(jì)程序，從鍵盤(pán)輸入含X、Y的字符串，所編寫(xiě)的程序從輸入的字符串中的第一個(gè)字符開(kāi)始比擬，依次比擬下去，假設(shè)發(fā)現(xiàn)該字符串與該狀態(tài)圖不符，那么不屬于該狀態(tài)圖。該程序的主要編程思想為大量使用if判斷語(yǔ)句，以及一些簡(jiǎn)單的for循環(huán)語(yǔ)句。四、源程序代碼：#include<iostream>usingnamespacestd;#defineMAX200voidmain(){ chara[MAX]; cout<<"根據(jù)正規(guī)式R分成三個(gè)局部，即R1=XY*，R2=YX*Y，R3=XYX"<<endl; cout<<"請(qǐng)輸入一段字符(僅含X或者Y):"<<endl; cin.get(a,200); intn;//所輸入字符串的長(zhǎng)度 for(inti=0;i!=MAX;++i)//計(jì)算編碼的長(zhǎng)度n { if(a[i]=='\0') { n=i; break; } } if(a[0]=='X') { if(a[1]=='\0') {cout<<"屬于正規(guī)式R1=XY*"<<endl; } elseif(a[1]=='Y') { if(a[2]=='\0') { cout<<"屬于正規(guī)式R1=XY*"<<endl; } elseif(a[2]=='X'&&a[3]=='\0') { cout<<"屬于正規(guī)式R3=XYX"<<endl; } else { for(i=2;i<n;) { if(a[i]=='Y') i++; else break; } if(i==n) { cout<<"屬于正規(guī)式R1=XY*"<<endl; } else { cout<<"不屬于正規(guī)式R"<<endl; } } } else { cout<<"不屬于正規(guī)式R"<<endl; } } elseif(a[0]=='Y') { if(a[1]=='Y'&&a[2]=='\0') { cout<<"屬于正規(guī)式R2=YX*Y"<<endl; } elseif(a[n-1]=='Y') { if(a[1]=='X') { for(i=1;i<n-1;) { if(a[i]=='X') { i++; } else { break; } } if(i==n-1) { cout<<"屬于正規(guī)式R2=YX*Y"<<endl; } else { cout<<"不屬于正規(guī)式R"<<endl; } } } else { cout<<"不屬于正規(guī)式R"<<endl; } } else { cout<<"不屬于正規(guī)式R"<<endl; }}五、測(cè)試用例1.當(dāng)從鍵盤(pán)輸入“XYYYYYYY“時(shí)，判斷屬于正規(guī)式R1=XY*.2.當(dāng)從鍵盤(pán)輸入YXXXXXXY時(shí)，判斷屬于正規(guī)式R2=YX*Y.當(dāng)從鍵盤(pán)輸入XYX時(shí)，判斷屬于正規(guī)式R3=XYX.當(dāng)輸入為XYYX時(shí)，不符合正規(guī)式R.5.當(dāng)輸入為YXXYX時(shí)，不符合正規(guī)式R.六、實(shí)驗(yàn)總結(jié)通過(guò)本次實(shí)驗(yàn)，使我對(duì)正規(guī)式轉(zhuǎn)成相應(yīng)的NFA、DFA以及最小DFA的知