【導(dǎo)讀】definition,suchas“IF”,“FOR”.procedure,functionandsoon,suchas:“index”,“count”.suchas“,”,“:”,“;”.

　　

【正文】 ε—CLOSURE（ I） （ 1） If P∈ I， then P∈ ε—CLOSURE（ I）； （ 2） If P∈ I， then P’∈ ε—CLOSURE （ I） , while P’ is the next state start from P on the path of ε. 52 ? The definition of Ia is: Ia means that I and J are all the subset state of K, J is the next state begins from I on the path a (or jump over some path of ε before state J or after state J) Ia=ε—CLOSURE（ J） Note: ε—CLOSURE（ I） is the subset of K. 53 ? Example ? The NFA of regular expression (a|b)*ab is shown below ? The translation system of regular expression (a|b)*ab ? 圖 正則式 (a|b)*ab的轉(zhuǎn)換系統(tǒng) 54 If we want to construct DFA from the translation system, we should remove theεin , and reconstruct it. . The state set K=｛ 1,2,3,4,5,6,7,8,9,10,11,12｝ 。 If subset I=｛ 1｝ , then ε—CLOSURE(I)= {1, 2, 3, 4, 8, 9}= Q0 M(Q0, a) = Ia={5,7,8,9,2,3,4,10,11} = Q1 M (Q0, b) = Ib = {6,7,8,9,2,3,4} = Q2 M (Q1, a) = Ia = Q1 M (Q1, b) = Ib = {6,7,8,9,2,3,4,12} = Q3 M (Q2, a) = Ia = Q1 M (Q2, b) = Ib = Q2 M (Q3, a) = Ia = Q1 M (Q3, b) = Ib = Q2 55 ? The state set is reconstructed and is shown by Figure . 56 Now we should minimize the DFA above. (1)States are divided into two state sets: terminal state set 3, and nonterminal state that include state 0,1,2. (2)Judge if states0,1,2 are equivalence states. M(Q0, a) = Q1 M (Q0, b) = Q2 M(Q1, a) = Q1 M (Q1, b) = Q3 M (Q2, a) = Q1 M (Q2, b) = Q2 The next state of state 1 is not in nonterminal states set when input character b, so the nonterminal states set is divided into state set 1 and state set 0, 2 . . 57 ? States 0 and 2 behave the same way, so they are equivalence states and can be merged. ? The minimun of DFA is shown by 58 ? An example for constructing DFA from regular expression ? Example The unsigned digital is “d…d. d…dESd…d”, it includes four regular expressions: dd* ｛ A1｝ d*dd* ｛ A2｝ d*ESdd* ｛ A3｝ d*dd*ESdd* ｛ A4｝ while VT=｛ 0, … , 9, , +, , E｝ d = 0|1|…|9 s= +||ε 59 ? What we want to do is to translate the expression into DFA, the transition includes three steps. Firstly create transition diagram for A1， A2， A3 and A4. Secondly, transfer the NFA to FA. Finally, to minimize the FA. (1)The transition diagram of A1， A2， A3 and A4 . Unsigned digital NFA is shown by . 60 (2)Transfer the NFA to FA The state of NFA are ｛ 0, 1, … ,15 ｝ ,the start state is ｛ 0｝ ,the leaving state are ｛ 2, 5, 9, 15｝ , input symbol are VT=｛ d, , E, S｝ ε—CLSOURE (｛ 0｝ ) =｛ 0, 1, 3, 6, 10｝ Id、 I.、 IS、 IE are shown in Table bination of four FA is shown by . 61 62 ? Reconstruction of Table is shown by Table 63 ? So the DFA is shown by Figure . 64 (3)Minimum the FA K=｛ A, B, C, D, E, F, G, H, I , J｝ The subset are K1=｛ A, C, D, F, G, I｝ K2=｛ B, E, H, J｝ Among set K1， set F and set I, set D and set G are equivalent。 so set K1 is divided into four subsets： ｛ A｝、｛ C｝、｛ D｝、｛ F｝ Similarly, among K2， set H and set J are equivalent,K2 is divided into three subsets： ｛ B｝、｛ E｝、｛ H｝ 65 ? The minimum states are shown by Figure and Table 66 67 ? The program and result of example is shown below. 68 69 70 71 ? The result of example is shown by