DFA和NFA等效語言

Question

我被要求構建一個DFA A和NFA B，使L（D）= L（N）滿足一些特定的條件。我不是在尋求解決方案或答案;我只是想確保我有正確的方法來解決這個問題。

首先，我對「構建」這個字眼有點困惑。他們只是想要一臺自動機繪製？那會被認爲是「內置的」嗎？

我正在考慮繪製符合該條件的NFA B.然後使用繪圖，我將構建一個等效的DFA A.有一個定理說，等價的自動機具有相同的語言。所以我不必再做任何事情來顯示L（A）= L（B）是對的嗎？

謝謝！

Answer 1

這聽起來是正確的。只需構造任何接受語言L（A）的NFA A.然後確定該NFA生成DFA B.DFA B也應接受L（A）。 DFA和NFA在他們接受的語言中是相同的。