編譯原理課程設(shè)計--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實現(xiàn)-其他專業(yè)-wenkub.com
2025-01-15 02:55 本頁面
【正文】 cout其中終態(tài)為： endnodeendl。(md[i].ltab)) ednode+=md[i].ltab。i++) for(j=0。 } } break。nm。klen。 cout{d[i]}=md[i].ltabendl。i++) { md[i].ltab=39。 ()。im。 } //coutsta=staendl。 j。 } else if(sta[0]!=x+48) { d[m]+=d[i][j]。ny。 y=m。i++) { //coutd[i]=d[i]endl。 ()。 coutendlDFA 如下： endl。 } 第 19 頁，共 22 頁 for(i=0。kh。 for(j=0。 NODE+=t[i].ltab。 t[i].()。 coutendl重命名： endl。 } } coutendl狀態(tài)轉(zhuǎn)換矩陣如下： endl。 if(flag) break。j++) { paixu(t[i].jihe[j])。jt[i].jihe[k].length()。k++) { //coutt[i].jihe[k]。mlen。ih。 h=1。 return。 第 17 頁，共 22 頁 cinendnode。amp。iN。 /*for(j=0。i++) { cinb[i].first。 string jh[MAXS],endnode,ednode,sta。 } coutendl。jlen。 39。 coutendlendl。ilen。([m][i]==b[j].first[0])) if([m].find(b[j].last[0])[m].length()) [m]+=b[j].last[0]。i++) for(j=0。amp。ik。he,int m,edge b[]) { int i,j,k,l。kN。 a[i+1]=b。j++) for(i=0。a) { 第 14 頁，共 22 頁 int i,j。ia。 string jihe[MAXS]。 string change。 string NODE。書本只能教給我們基礎(chǔ)知識 ,要怎樣運用 ,將那些知識真正吸收 ,轉(zhuǎn)化為自己的智慧 ,只有通過實 踐才能達到。 ： 通過這次課程實踐設(shè)計，讓我對課堂上老師所講到的不確定和確定有限自動機有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。 NFA的確定化是編譯過程中一個重要的部分，由于本程序的輸入很多，而且有多種格式的輸入，所以輸入時必須非常小心細致。 以下面的基于字母表 Σ ={a,b}上的具有ε 轉(zhuǎn)移的非確定有限自動機 M為例。 狀態(tài)集合 I 的 a 弧轉(zhuǎn)換 Ia:定義為一狀態(tài)集，是指從狀態(tài)集 I出發(fā)先經(jīng)過 a弧后再經(jīng)過若干條 ε 弧而能到達的狀態(tài)的集合。用雙箭頭 =標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以 1，非終態(tài)標(biāo)以 0. U S V Q a b a a a,b b b 第 5 頁，共 22 頁 狀態(tài) 字符 a b S U V 0 U Q V 0 V U Q 0 Q Q Q 1 3．從 NDF 到 DFA 的等價變化步驟 事 實已經(jīng)證明了不管是非確定的有限自動機 M 還是具有ε 轉(zhuǎn)移的非確定的有限自動機，都可以找到一個與之等價的確定有限自動機，使得 L（ M） =L（ M’）。 有限自動機（ Finite Automate）是用來模擬實物系統(tǒng)的數(shù)學(xué)模型，它包括如下五個部分： ? 有窮狀態(tài)集 States ? 輸入字符集 Input symbols ? 轉(zhuǎn)移函數(shù) Transitions ? 起始狀態(tài) Start state ? 接 受狀態(tài) Accepting state(s) 實踐目的 （ 1）設(shè)計、編制、調(diào)式一個有窮自動機程序，加深對 NFA 轉(zhuǎn)換為 DFA的原理的理解。 對于任意的一個不確定有限自動機（ NFA）都會存在一個等價的確定的有限自動機（ DFA），即 L(N)=L(M)。不確定的有限自動機則相反，在某種狀態(tài)下，面臨一個特定的符號是存在不止一個轉(zhuǎn)換，即是可以允許進入一個狀態(tài)集合。 在非確定的有限自動機 NFA 中 ,由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個 NFA 對符號串的識別就必然是一個試探的過程。本文主要是介紹如何將 NFA轉(zhuǎn)換為與之等價的簡化的 DFA，通過具體實例，結(jié)合圖形，詳細說明轉(zhuǎn)換的算法原理。 （ 2）掌握 NFA 確定化的過程。 轉(zhuǎn)換思路 由非確定的有限自動機出發(fā)構(gòu)造與之等價的確定的有限自動機的辦法是確定的有限自動機的狀態(tài)對應(yīng)于非確定的有限自動機的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA 的每一個狀態(tài)對應(yīng) NFA 的一組狀態(tài)?？梢詫懽鳎? Ia= ε closure(J)， J=move(I,a),其中， J是從 I 中任一狀態(tài)出發(fā)經(jīng)過一條 a 弧到達的狀態(tài)集合，記為 move(I,a)。 步驟 1： 以 I， Ia、 Ib 等為列做表，其中 I列第一行的內(nèi)容是初態(tài)的ε 閉包所得到的狀態(tài)集合。對于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號前的是新狀態(tài)名，冒號后的是舊狀態(tài)名。很好的理解了子集法的演算過程。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目 ,我將會繼續(xù)努力 ,不斷增加自己的知識面 ,把編譯原理學(xué)習(xí)的更好。 //結(jié)點集合 string CHANGE。 string last。 }。i++) cout39。 char b。i()。 } } void eclouse(char c,string amp。k++) { if(c==b[k].first[0]) if(b[k].change==*) { if((b[k].last)()) he+=b[k].last。 k=()。i++) for(j=0。([i]==b[j].first[0])) if([m].find(b[j].last[0])[m].length()) [m]+=b[j].last[0]。jN。 } //輸出 void output
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1