編譯原理課程設(shè)計(jì)--NFA轉(zhuǎn)化為DFA的轉(zhuǎn)換算法及實(shí)現(xiàn)

1、編譯原理課程實(shí)踐報(bào)告設(shè)計(jì)名稱(chēng)：NFA轉(zhuǎn)化為DFA勺轉(zhuǎn)換算法及實(shí)現(xiàn)二級(jí)學(xué)院：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：計(jì)科本091班姓名：林玉蘭學(xué)號(hào)：0904402102指導(dǎo)老師：-梁徳塞日期：_2012 年6月摘要確定有限自動(dòng)機(jī)確定的含義是在某種狀態(tài)， 面臨一個(gè)特定的符號(hào)只有一個(gè)轉(zhuǎn) 換，進(jìn)入唯一的一個(gè)狀態(tài)。不確定的有限自動(dòng)機(jī)則相反，在某種狀態(tài)下，面臨一 個(gè)特定的符號(hào)是存在不止一個(gè)轉(zhuǎn)換，即是可以允許進(jìn)入一個(gè)狀態(tài)集合。在非確定的有限自動(dòng)機(jī)NFA中，由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù) 狀態(tài)中進(jìn)行選擇，故一個(gè)NFA對(duì)符號(hào)串的識(shí)別就必然是一個(gè)試探的過(guò)程。這種不確定性給識(shí)別過(guò)程帶來(lái)的反復(fù)，無(wú)疑會(huì)

2、影響到FA的工作效率。而DFA則是確定的,將NFA轉(zhuǎn)化為DFA將大大提高工作效率,因此將NFA轉(zhuǎn)化為DFA是有其一定必 要的。對(duì)于任意的一個(gè)不確定有限自動(dòng)機(jī)(NFA都會(huì)存在一個(gè)等價(jià)的確定的有限 自動(dòng)機(jī)(DFA，即L(N)=L(M)。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價(jià)的簡(jiǎn) 化的DFA通過(guò)具體實(shí)例，結(jié)合圖形，詳細(xì)說(shuō)明轉(zhuǎn)換的算法原理。關(guān)鍵詞：有限自動(dòng)機(jī)；確定有限自動(dòng)機(jī)(DFA，不確定有限自動(dòng)機(jī)(NFAAbstractFinite automata is determinate and indeterminate two class. Determine the meaning is in a

3、certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.Non deterministic finite state

4、automata NFA, because of some state are transferred from a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DFA

5、 is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to conver

6、t NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conversion.Keywords: ： finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA目錄1. 前言 ： 1.1背景1.2 實(shí)踐目的 1.2 課程實(shí)踐的意義 2. NF

7、A和DFA的概念 22.1 不確定有限自動(dòng)機(jī) NFA 22.2 確定有限自動(dòng)機(jī) DFA 33. 從NDF到DFA的等價(jià)變化步驟 53.1 轉(zhuǎn)換思路 53.2. 消除空轉(zhuǎn)移 53.3 子集構(gòu)造法 74 程序?qū)崿F(xiàn) 94.1 程序框架圖 94.2 數(shù)據(jù)流程圖 94.3 實(shí)現(xiàn)代碼 104.4 運(yùn)行環(huán)境 104.5 程序?qū)崿F(xiàn)結(jié)果 105. 用戶(hù)手冊(cè) 126. 課程總結(jié)： 127. 參 考 文 獻(xiàn) 128. 附錄 131. 前言：A A1.1 背景有限自動(dòng)機(jī)作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所 定義的語(yǔ)言和正規(guī)式所表示的集合， 引入有窮自動(dòng)機(jī)這個(gè)理論， 正是為詞法分析 程序的自動(dòng)構(gòu)造尋

8、找特殊的方法和工具。有限自動(dòng)機(jī)( Finite Automate )是用來(lái)模擬實(shí)物系統(tǒng)的數(shù)學(xué)模型，它包括 如下五個(gè)部分：? 有窮狀態(tài)集 States? 輸入字符集 Input symbols? 轉(zhuǎn)移函數(shù) Transitions? 起始狀態(tài) Start state? 接受狀態(tài) Accepting state(s)1.2 實(shí)踐目的(1) 設(shè)計(jì)、編制、調(diào)式一個(gè)有窮自動(dòng)機(jī)程序，加深對(duì) NFA轉(zhuǎn)換為DFA的原理 的理解。(2) 掌握NFA確定化的過(guò)程。1.2 課程實(shí)踐的意義通過(guò)本課程設(shè)計(jì)教學(xué)所可以使我們充分理解和掌握 NFA DFA以及NFA確定 化過(guò)程的相關(guān)概念和知識(shí)， 理解和掌握子集法的相關(guān)知識(shí)和應(yīng)

9、用， 編程實(shí)現(xiàn)對(duì)輸 入NFA轉(zhuǎn)換成DFA輸出的功能。2. NFA 和 DFA 的概念2.1 不確定有限自動(dòng)機(jī) NFA即非確定有限自動(dòng)機(jī), 即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所NFA(nondeterministic finite-state automata)個(gè)非確定的有限自動(dòng)機(jī)NFA M是一個(gè)五元式：NFA M ' =(S, 2U £ , S , SO, F)其中S 有限狀態(tài)集，2U £ 輸入符號(hào)加上 射出的弧可以是工中一個(gè)字符或是& .SO 初態(tài)集F終態(tài)集轉(zhuǎn)換函數(shù) S X2 U £ 2S(2S -S的幕集一S的子集構(gòu)成的集合)例 1 ： NFA M=(S,P,

10、Z,O,1,f,s,p,z)其中f(s,O)=pf(z,O)=pf(p,1)=zf(z,1)=pf(s,1)=s,zNFA的狀態(tài)圖表示如下：第2 頁(yè)，共22頁(yè)NFA矩陣表示:狀態(tài)f字符01SPS,Z0PZ0ZPP12.2確定有限自動(dòng)機(jī)DFADFA（deterministicfinite-stateautomata）即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī)DFA M是一個(gè)五元式：M=（S, 藝，S , SO, Z）其中：S 有限狀態(tài)集工一輸入字母表S 映射函數(shù)（也稱(chēng)狀態(tài)轉(zhuǎn)換函數(shù)）S x藝SS (s,a)=S ',S, S ' S, a 藝S0初始狀態(tài)S0 SZ終止?fàn)顟B(tài)集ZS例 2:

11、 DFAM=(S,U,V,Q,a,b,f,s,Q)其中f的定義為:f(S,a)=Uf(S,b)=Vf(U,a)=Qf(U,b)=Vf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=QDFA的狀態(tài)圖表示：假如DFAM含有m個(gè)狀態(tài)，n個(gè)輸入符，那么這個(gè)狀態(tài)含有 m個(gè)節(jié)點(diǎn)，每個(gè) 節(jié)點(diǎn)最多有n個(gè)弧射出，整個(gè)圖整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié) 點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“ +”, 若f(ki ,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀結(jié)點(diǎn)kj畫(huà)標(biāo)記為a的?。篴aUSaVba,bDFA矩陣表示：一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，

12、列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新?tīng)顟B(tài)，即k行a列為f(k,a)的值。用雙箭頭=>標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0.宀狀態(tài)、字符abSUV0UQV0VUQ0QQQ13. 從NDF到DFA的等價(jià)變化步驟事實(shí)已經(jīng)證明了不管是非確定的有限自動(dòng)機(jī) M還是具有&-轉(zhuǎn)移的非確定的 有限自動(dòng)機(jī)，都可以找到一個(gè)與之等價(jià)的確定有限自動(dòng)機(jī)，使得L( M =L(M)3.1轉(zhuǎn)換思路由非確定的有限自動(dòng)機(jī)出發(fā)構(gòu)造與之等價(jià)的確定的有限自動(dòng)機(jī)的辦法是確 定的有限自動(dòng)機(jī)的狀態(tài)對(duì)應(yīng)于非確定的有限自動(dòng)機(jī)的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的

13、一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在NFA讀入 一個(gè)輸入符號(hào)后可能到達(dá)的所有狀態(tài)，也就是說(shuō)，在讀入符號(hào)串a(chǎn)1a2a3an之后，該DFA處在這樣一個(gè)狀態(tài)，該狀態(tài)表示這個(gè) NFA的狀態(tài)的一個(gè)子集T,而T 是從NFA的開(kāi)始狀態(tài)沿著某個(gè)標(biāo)記為a1a2a3an的路徑可以到達(dá)的那些狀態(tài)。3.2. 消除空轉(zhuǎn)移.消除N形式的產(chǎn)生式，即消除空轉(zhuǎn)移。狀態(tài)集合I的a弧轉(zhuǎn)換la:定義為一狀態(tài)集，是指從狀態(tài)集I出發(fā)先經(jīng)過(guò)a弧后再經(jīng)過(guò)若干條&弧而能到達(dá)的狀 態(tài)的集合。可以寫(xiě)作：la= &-closure(J) ，J=move(l,a),其中，J是從I中任 一狀態(tài)出發(fā)經(jīng)過(guò)一條a弧到達(dá)的狀態(tài)集合，記為mov

14、e(I,a)。s表示NFA的狀態(tài)，T表示NFA的狀態(tài)集合，a表示一個(gè)in put symbol£ -tra nsitio n（&轉(zhuǎn)換）就是說(shuō) in put symbol 為&時(shí)的 tran sitio n（轉(zhuǎn)換）操作(operati on)描述(descripti on)£-closure(s)從NFA的狀態(tài)s出發(fā)，只通過(guò)£ -transition到達(dá)的NFA的狀態(tài)集合£-closure(T)NFA的集合T中的狀態(tài)p,只通過(guò)£ -transition到達(dá)的NFA的狀態(tài)集合，再求這些集合的交集。用數(shù)學(xué)表達(dá)就是p|p屬于£

15、-closure（t） , t屬于 Tmove(T,a)NFA的集合，這個(gè)集合在in put symbol為a,狀態(tài)為T(mén)中任 意狀態(tài)情況下，通過(guò)一個(gè)轉(zhuǎn)換得到的集合例如：對(duì)于以下?tīng)顟B(tài)圖中：£ -closure(0)=0,1,2,4,7在這里設(shè)匸0,124,7，則因?yàn)橛衜ove(l,a)=3,8=J, 所以Ia= £ -closure(J)=£ -closure(3,8)=1,2,3,4,6,7,8£3.3子集構(gòu)造法確定化每個(gè)多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù)，具體轉(zhuǎn)換，采用子集構(gòu)造法。以下面的基于字母表 工=a,b上的具有& -轉(zhuǎn)移的非確定有限自動(dòng)

16、機(jī) M為例。步驟1:以I , la、Ib等為列做表，其中I列第一行的內(nèi)容是初態(tài)的& -閉包所得到的狀態(tài)集合。并以此為I計(jì)算la、lb等，而 且在所計(jì)算出的la、lb等中 若有新的狀態(tài)集產(chǎn)生，就重復(fù)以此新的集合為 l再此計(jì)算la、lb等，直到在所 得的la、lb等中不再產(chǎn)生新的狀態(tài)集為止。llalbx,5,15,1,35,1,45,1,35,1,3,2,6,y5,1,45,1,45,1,35,1,4,2,6,y5,1,3,2,6,y5,1,3,2,6,y5,1,4,6,y5,1,4,2,6,y5,1,3,6,y5,1,4,2,6,y5,1,4,6,y5,1,3,6,y5,1,4,2,6,

17、y5,1,3,6,y5,1,3,2,6,y5,1,4,6,y步驟2:在上表中將原NFA初態(tài)的& -閉包作為轉(zhuǎn)換后的DFA的初態(tài)，包含原NFA 終態(tài)的狀態(tài)作為轉(zhuǎn)換后的DFA的終態(tài)，并進(jìn)行重新編號(hào)得到轉(zhuǎn)換后的DFA的狀態(tài) 轉(zhuǎn)移矩陣如下：abx,5,115,1,325,1,43 o5,1,325,1,3,2,6,y45,1,43 05,1,435,1,3 25,1,4,2,6,y55,1,3,2,6,y45,1,3,2,6,y45,1,4, 6,y65,1,4,2,6,y55,1,3, 6,y75,1,4,2,6,y55,1,4, 6,y65,1,3, 6,y75,1,4,2,6,y55,1

18、,3, 6,y75,1,3,2,6,y45,1,4, 6,y6第15頁(yè)，共22頁(yè)步驟3：畫(huà)出轉(zhuǎn)換后的DFA的狀態(tài)圖:4.1程序框架圖4.2數(shù)據(jù)流程圖4程序?qū)崿F(xiàn)NFA專(zhuān)化為NFA圖結(jié)構(gòu)NFA狀態(tài)表DFA圖結(jié)構(gòu)初始化狀態(tài)轉(zhuǎn)換矩陣狀 態(tài) 轉(zhuǎn) 換 操 作4.3實(shí)現(xiàn)代碼(見(jiàn)附錄)4.4運(yùn)行環(huán)境(1) 開(kāi)發(fā)平臺(tái)：Microsoft visual C+6.0(2) 運(yùn)行平臺(tái)： Win dows xp/Wi ndows 20004.5程序?qū)崿F(xiàn)結(jié)果實(shí)現(xiàn)NFA例題為：NFA M=(S,P,Z,0,1,f,s,p,z)其中f(s,O)=pf(z,O)=pf(P,1)=zf(z,1)=pf(s,1)=s,z根據(jù)例題輸

19、入NFA各邊的信息得出結(jié)果如下圖:5. 用戶(hù)手冊(cè)本程序應(yīng)在Microsoft Visual C+ 6.0 下運(yùn)行。NFA的確定化是編譯過(guò)程 中一個(gè)重要的部分， 由于本程序的輸入很多， 而且有多種格式的輸入， 所以輸入 時(shí)必須非常小心細(xì)致。 對(duì)于狀態(tài)轉(zhuǎn)換矩陣的表示， 冒號(hào)前的是新?tīng)顟B(tài)名， 冒號(hào)后 的是舊狀態(tài)名。對(duì)于轉(zhuǎn)化后的DFA表示，3個(gè)數(shù)據(jù)分別表示為起始狀態(tài)、接受字 符和到達(dá)狀態(tài)，例如（ 0,1,1 ）表示為新?tīng)顟B(tài) 0 接受字符 1 到達(dá)新字符狀態(tài) 1。 運(yùn)行結(jié)果因?yàn)檗D(zhuǎn)換字符輸入順序的不同， 得出的結(jié)果有可能與筆算得出的順序有 所不同，但是結(jié)果依然是正確。6. 課程總結(jié)：通過(guò)這次課程實(shí)踐設(shè)計(jì)，

20、 讓我對(duì)課堂上老師所講到的不確定和確定有限自動(dòng) 機(jī)有了更深的理解， 理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。 很好的理解了子集法的 演算過(guò)程。經(jīng)過(guò)多次試驗(yàn)，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運(yùn)行，當(dāng) 錯(cuò)誤操作或輸入錯(cuò)誤數(shù)據(jù)時(shí)，程序?qū)?yīng)錯(cuò)誤自動(dòng)關(guān)閉。經(jīng)過(guò)這次課程設(shè)計(jì), 也讓我深刻的認(rèn)識(shí)到實(shí)踐才是最重要的。書(shū)本只能教給我們基礎(chǔ)知識(shí), 要怎樣運(yùn)用 ,將那些知識(shí)真正吸收 , 轉(zhuǎn)化為自己的智慧 , 只有通過(guò)實(shí)踐才能達(dá)到。 編譯原理是一 門(mén)實(shí)用性很強(qiáng)，對(duì)我們的專(zhuān)業(yè)很有幫助的科目 , 我將會(huì)繼續(xù)努力 , 不斷增加自己的 知識(shí)面, 把編譯原理學(xué)習(xí)的更好。同時(shí)我也發(fā)現(xiàn)自己對(duì)于有限自動(dòng)機(jī)的知識(shí)掌握得還不是很多， 在這

21、次課程實(shí) 踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識(shí)。7. 參 考 文 獻(xiàn)1）楊路明、郭浩志 .C 語(yǔ)言程序設(shè)計(jì)教程 .2003 年 12 月第 1版. 北京: 北京郵 電大學(xué)出版社 .20052）陳火旺.程序設(shè)計(jì)語(yǔ)言編譯原理 .2000 年1月第 3版. 北京:國(guó)防工業(yè)出版 社.2006.46-51（3）嚴(yán)蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.1997年4月第1版.北京：清華大 學(xué)出版社 .20054）王曉東編著 . 計(jì)算機(jī)算法設(shè)計(jì)與分析 . 電子工業(yè)出版社 .20048. 附錄NFA轉(zhuǎn)換為DFA采用C+編程實(shí)現(xiàn)代碼如下 #include<iostream> #i

22、nclude<string>#define MAXS 100 using namespace std;string NODE; / 結(jié)點(diǎn)集合 string CHANGE; / 終結(jié)符集合 int N; /NFA 邊數(shù) struct edgestring first;string change;string last;struct chan string ltab;string jiheMAXS;void kong(int a) int i;for(i=0;i<a;i+) cout<<' '/ 排序 void paixu(string &a)

23、 int i,j;char b;for(j=0;j<a.length();j+)for(i=0;i<a.length();i+)if(NODE.find(ai)>NODE.find(ai+1)b=ai;ai=ai+1;ai+1=b;void eclouse(char c,string &he,edge b)int k;for(k=0;k<N;k+)if(c=bk.first0)if(bk.change="*")if(he.find(bk.last)>he.length()he+=bk.last;eclouse(bk.last0,he,b

24、);void move(chan &he,int m,edge b)int i,j,k,l;k=he.ltab.length();l=he.jihem.length();for(i=0;i<k;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.ltabi=bj.first0)if(he.jihem.find(bj.last0)>he.jihem.length()he.jihem+=bj.last0;for(i=0;i<l;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0

25、)&&(he.jihemi=bj.first0)if(he.jihem.find(bj.last0)>he.jihem.length()he.jihem+=bj.last0;/ 輸出void outputfa(int len,int h,chan *t)int i,j,m;cout<<" I "for(i=0;i<len;i+)cout<<'I'<<CHANGEi<<" "cout<<endl<<""<<en

26、dl;for(i=0;i<h;i+)cout<<' '<<ti.ltab;m=ti.ltab.length();for(j=0;j<len;j+)kong(8-m);m=ti.jihej.length();cout<<ti.jihej;cout<<endl;void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;coutvv"請(qǐng)輸入NFA各邊信息，分別為：起點(diǎn) 條件空為

27、* 終點(diǎn)，最后以#結(jié)束: "<<endl;for(i=0;i<MAXS;i+)cin>>bi.first;if(bi.first="#") break;cin>>bi.change>>bi.last;N=i;/*for(j=0;j<N;j+)cout<<bj.first<<bj.change<<bj.last<<endl;*/for(i=0;i<N;i+)if(NODE.find(bi.first)>NODE.length()NODE+=bi.f

28、irst;if(NODE.find(bi.last)>NODE.length()NODE+=bi.last;if(CHANGE.find(bi.change)>CHANGE.length()&&(bi.change!="*")CHANGE+=bi.change;len=CHANGE.length();cout<<" 結(jié)點(diǎn)中屬于終態(tài)的是： "<<endl;cin>>endnode;for(i=0;i<endnode.length();i+) if(NODE.find(endnodei)&

29、gt;NODE.length()cout<<" 所輸終態(tài)不在集合中，錯(cuò)誤！ "<<endl; return; /cout<<"endnode="<<endnode<<endl; chan *t=new chanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b); / 求 /cout<<t0.ltab<<endl;for(i=0;i<h;i+)for(j=0;j<ti.ltab.length();j+)f

30、or(m=0;m<len;m+) eclouse(ti.ltabj,ti.jihem,b); /for(k=0;k<len;k+)/cout<<ti.jihek<<"->"move(ti,k,b); /求 move(I,a)/cout<<ti.jihek<<endl; for(j=0;j<ti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); / for(j=0;j<len;j+)e-clouse求 e-clouse求 e-clousepaixu(

31、ti.jihej); / 對(duì)集合排序以便比較 for(k=0;k<h;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&&ti.jihej.length()th+.ltab=ti.jihej;cout<<endl<<" 狀態(tài)轉(zhuǎn)換矩陣如下： "<<endl; outputfa(len,h,t); / 輸出狀態(tài)轉(zhuǎn)換矩陣 / 狀態(tài)重新命名 string *d=new stringh;NODE.erase();cout<<endl<<

32、" 重命名： "<<endl;for(i=0;i<h;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab='A'+i;NODE+=ti.ltab;cout<<''<<sta<<"="<<ti.ltab<<endl;for(j=0;j<endnode.length();j+)if(sta.find(endnodej)<sta.length()d1=ednode+=ti.ltab;for(k=0;k<h;k

33、+)for(m=0;m<len;m+)if(sta=tk.jihem)tk.jihem=ti.ltab;for(i=0;i<NODE.length();i+) if(ednode.find(NODEi)>ednode.length() d0+=NODEi;endnode=ednode; cout<<endl<<"DFA 如下： "<<endl; outputfa(len,h,t); / 輸出 DFA cout<<" 其中終態(tài)為： "<<endnode<<endl;

34、/DFA 最小化 m=2;sta.erase();flag=0;for(i=0;i<m;i+)/cout<<"d"<<i<<"="<<di<<endl;for(k=0;k<len;k+) /cout<<"I"<<CHANGEk<<endl; y=m;for(j=0;j<di.length();j+)for(n=0;n<y;n+)if(dn.find(tNODE.find(dij).jihek)<dn.length()|tNODE.fin d(dij).jihek.length