この非決定論的なFSAを決定論的なものに変換するにはどうすればよいですか？

Question

決定論1、特にテーブルに、この非決定FSA

を変換する方法を疑問に思います。

私はこれまでのところ、これを持っているが、立ち往生しています：

どのように私はBHMQを割り当てていますか？状態1の場合、4桁はありませんか？ （C、I、N、R）？

Answer 1

あなたが探しているコンセプトは、いわゆるpower set constructionです。最初のオートマトンから、そのサブセットのすべてのセットであるそのパワーセットを、結果として得られるオートマトンの状態セットとすることによって、状態セットが変換される。最終状態は、初期最終状態の少なくとも1つを含む状態である。

結果として得られるオートマトンは、受け入れられた言語が等しいという意味で最初のオートマトンに相当します。しかし、状態の数は指数関数的に増加することがあります。