DFA和Loop，NFA和遞歸之間是否存在關係？

Question

我聽說DFA可以通過Loop進行模擬，而NFA可以通過遞歸方法進行模擬。我不明白這是如何工作的。任何人都可以給我一個例子嗎？

Answer 1

從某種意義上講，當然。基於當前狀態，可以通過編寫一個do...while循環和一個switch語句來輕鬆地模擬DFA，而您可以將NFA的模擬器想象爲在樹上執行搜索（深度優先搜索是遞歸的，儘管您可以像想象一下廣度優先搜索）。這裏沒有任何形式，只是對你如何實現模擬器的一個隨意觀察。