構造非確定型有限自動機

Question

我做手寫詞法分析器。我需要繪製一個非確定性有限自動機，其中包含三個以前製作的有限自動機。我爲飛機，雲彩，跑道等關鍵詞製作了它們。我需要幫助，如何構建這三個自動機的通用自動機。我需要一些例子如何做到這一點？如果你知道請幫助我？

Answer 1

繪製飛機，雲彩和跑道自動機在啓動狀態之前留下一些空間。現在，抹掉他們的第一個狀態。在他們面前繪製一個新的，單個狀態。將它連接到帶有「a」過渡/邊緣的「irplane」自動機，將「r」邊緣「解開」，並將「c」邊緣連接到「大聲」。而已。完成。

對於更一般的情況，它比較複雜： 首先，畫出你的每個自動機（例如飛機，雲和跑道），在它們開始的地方留下一些空的空間。接下來，在他們開始之前繪製一個狀態，並通過自由邊將其連接到飛機的起點，雲和跑道自動機的舊開始狀態。 （自由邊也稱爲ε邊，ε邊，λ邊或λ邊）。

接下來，您對它們執行子集構建算法，您可以在其上找到YouTube視頻教程。還有一個online subset construction algorithm tool會將非確定性有限自動機轉換爲確定性有限自動機（DFA）。該過程稱爲確定。

一旦擁有了DFA，就可以使用它來構建驅動掃描器的狀態，操作和查找表。這是它自己的蠕蟲病毒。人們通常使用像Lex或Flex這樣的掃描生成器來自動化。您可以在線使用的一個類似的，用戶友好的工具是the Online Scanner Generator。

airplane:airplane 
cloud:cloud 
runway:runway 

它會給你一個DFA爲，像這樣：

你可以通過提供以下投入使用，使圖表