上篇講述確定有窮自動機和不確定有窮自動機，本篇講述不確定有窮自動機和確定有窮自動機之間的轉換。從百度文庫中找到一個示例感覺很合適。 如圖所示：  **1．具有ε動作的NFA狀態轉換表** <table border="1" cellspacing="0" cellpadding="0"><tbody><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">? ? ? ? ? ? ? ? ? ? ? ? ?a ? ? ? ? ? ? ? ? ? ? ? ?</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">? ? ? ? ? ? ? ? ? ? ? ? b ? ? ? ? ? ? ? ? ? ? ? ?</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?ε ? ? ? ? ? ? ? ? ? ? ? ? ? ?</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">0</span></strong></p></td><td valign="top"><p align="center"><a name="OLE_LINK1"><strong><span style="font-size:14px">Φ</span></strong></a></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">1, 7</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">1</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">2, 4</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">2</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">3</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">3</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">4</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">5</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">5</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">1, 7</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">7</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">8</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">8</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">9</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">9</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr></tbody></table> **2．分別求ε-closure** **ε-closure（I）就是狀態集I中，任意狀態S經過任意的?ε能到達的狀態集合。** ~~~ ???????????????ε-closure(0) = {0,1,2,4,7} ???????????????ε-closure(1) = {1,2,4} ? ? ? ? ? ? ??ε-closure(2) = {2} ? ? ? ? ? ? ??ε-closure(3) = {1,2,3,4,6,7} ? ? ? ? ? ? ??ε-closure(4) = {4} ? ? ? ? ? ? ??ε-closure(5) = {1,2,4,5,6,7} ? ? ? ? ? ? ??ε-closure(6) ={1,2,4,6,7} ? ? ? ? ? ? ??ε-closure(7) = {7} ? ? ? ? ? ? ??ε-closure(8) = {8} ? ? ? ? ? ? ??ε-closure(9) = {9} ~~~ **3．轉換算法：** **move（I，a）是從I中的某一狀態經過一條a弧而到達的狀態全體。** ~~~ ? ? ? ? ? ? ??ε-closure(0) ={0,1,2,4,7} = A ? ? ? ? ? ? ??ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8} = B ? ? ? ? ? ? ??ε-closure(move(A,b))=ε-closure({5})={1,2,4,5,6,7} = C ? ? ? ? ? ? ??ε-closure(move(B,a))=ε-closure({3,8}) = B ? ? ? ? ? ? ??ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D ? ? ? ? ? ? ??ε-closure(move(C,a))=ε-closure({3,8}) = B ? ? ? ? ? ? ??ε-closure(move(C,b))=ε-closure({5}) = C ? ? ? ? ? ? ??ε-closure(move(D,a))=ε-closure({3,8}) = B ? ? ? ? ? ? ??ε-closure(move(D,b))=ε-closure({5}) = C ~~~ **** **4．DFA的轉換表** <table border="1" cellspacing="0" cellpadding="0"><tbody><tr><td rowspan="2"><p align="center"><strong><span style="font-size:14px">? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 狀態 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??</span></strong></p></td><td width="379" colspan="2"><p align="center"><strong><span style="font-size:14px">? ? ? 輸入符號 ? ? ??</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">a</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">b</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">A</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">D</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">D</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr></tbody></table> **5．狀態轉換圖** **** 本篇到這里，編譯原理入門教程就到這里了，僅僅是編譯原理的初學者，請您多多指教哦 愿開心每一天~