正規表現を有限状態マシン (FSM) に変換するアルゴリズムのヒントを教えてください。たとえば、正規表現を解析し、状態を FSM に適切に追加するアルゴリズムは? 参照またはより深いアイデアはありますか?
私はPythonでこれを書いています
6017 次
1 に答える
8
Michael Sipser のIntroduction to the Theory of Computation を使用します。第 1 章では、正規表現を決定論的または非決定論的な有限状態オートマトン (DFA または NFA) に変換するための詳細なアルゴリズムを、それらの同等性を証明するコンテキストで示します (DFA、NFA、および正規表現は、まったく同じクラスに一致する可能性があります)。文字列の）。
一般的な考え方は次のとおりです。正規表現を NFA に変換します。これは非常に簡単に実行できます (*はループで|、文字範囲は分岐点です)。次に、NFA を (はるかに大きな) DFA に変換します。これには、代替 NFA 状態のセットごとに 1 つの DFA 状態を作成することが含まれます。DFA は、最大で NFA 状態のセットのパワーセットと同数の状態を持ち (たとえば、3 つの状態を持つ NFA は、最大で 2^3 = 8 状態の DFA に変換できます)、バックトラックなしで任意のターゲット文字列を認識できます。 . 詳しくは本を読んでください。
于 2012-07-11T13:49:20.447 に答える