CS クラスの McNaughton-Yamada アルゴリズムを使用して DFA を構築する必要があります。問題は、アルゴリズムが補足資料であり、それが正確に何であるかがはっきりしないことです. 正規表現を指定してDFAを見つける方法ですか、それともDFAを見つけて最小化していますか? この件に関する情報が見つからないようです。
クラスで DFA を見つけた後にインストラクターが示した最小化ルーチンは、私たちの本で説明されている「マーク」最小化と何ら変わらないように見えるので、私は混乱しています。
お返事をありがとうございます、
ネイサン
http://swtch.com/~rsc/regexp/regexp1.htmlに、(NFA への正規表現および DFA への NFA の) アルゴリズムの説明があります。彼らは Thompson のバージョンを示しており、McNaughton-Yamada アルゴリズムは基本的に同じですが、正規表現から直接 DFA を生成すると主張しています。
「...McNaughton-Yamada 分析アルゴリズム。これにより、遷移テーブルが与えられた有限状態マシンによって受け入れられる単語を記述する正規表現が見つかります。修正されていないアルゴリズムは、n 状態マシンを表す 4n 項を生成します。この数は次のようになります。重複する計算を排除し、同じ状態図内の可能なパスに対応する高レベルの式を拒否することによって削減されます.残りの式は、アルゴリズムによって空の式とnullワードが自由に生成されるため、深刻な単純化の問題を提示します.
彼らのアルゴリズムは、通常、Thompson の研究とは別に取り上げられることはありません。Thompson のオリジナルは、正規表現からメモリ内のシミュレートされた NFA になりました。Thompson-McNaughton-Yamada アルゴリズムは、一時的なシミュレーションではなく、メモリに格納された実際の NFA に正規表現を変換する拡張機能です。
NFA を DFA (決定化) に変換することは、McNaughton または Yamada の拡張の一部ではありません。むしろ、サブセット構築(別名パワーセット構築) アルゴリズムを介して行われます。
Compiler Construction Toolkit の正規表現から NFA および DFAツールを使用して、Thompson-McNaughton-Yamada アルゴリズムとサブセット構築アルゴリズムが任意の正規表現で動作する様子を確認できます。