正規表現をNFAトランジションテーブルに変換する

Question

言語には関係ありませんが、正規表現をNFAテーブルに変換する方法を理解する必要があります。 たとえば、 "（ab）* + ba"は
になります。 T | | b |^
0 | N | 1 | 2
1 | 3 | N | N
2 | 4 | N | 3
3 | N | N | N
4 | N | 2 | N

誰かが私の正しい方向を指すのを手伝ったり、これがどのように行われたかを私に示してくれれば大いに感謝します。

編集：私は見てました：
http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html、私はまだ、最も外側の操作を見つけ、この

Answer 1

ファーストをプログラムする方法のアイデアを取得することができませんでした。あなたの例では、それは+です。 +がある場合は、左側のものか右側のもののいずれかを受け入れることができます。

Q s Q' 
q0 - M1 
q0 - M2 

は、私たちは出発点としてq0を持っていると我々はLHSによって生成された文字列を受け入れるマシンを表現するためにM1とM2を使用して：私たちは、次のように遷移を空（ラムダ、またはイプシロン）を使用して、NFAでこれをエンコードすることができますそれぞれ正規表現のRHSです。 q0と言うとき、ラムダ/イプシロン - 空の遷移でM1とM2に遷移します。つまり、どのパスがダウンするかを非決定的に選択することを意味します。遷移は、q0から、初期状態のM1とM2になります。

これで、LHSとRHSのそれぞれについて再帰的にプロセスを繰り返します。私たちはより簡単なので、RHSから始めることができます。ここで一番外側の操作は、（記号aとbの）連結です。連結を表現するために簡単である：ここ

Q s Q' 
q2 - M3 
M3 - M4 

、q2前からM2、及びM3とM4の初期状態を表すそのままの未の連結を、それぞれ、LHSとRHSを受け入れる未定機aおよびb。 q2をM3に遷移させると、M3の初期状態に遷移することを意味します。 M3がM4に遷移すると、M3のすべての受理状態がM4の初期状態に遷移することを意味します。

再帰的に進むには、aとbのマシンが必要です。

qが初期状態である

Q s Q' 
q x q' 

、xはシンボルであり、q'が受理状態である：これらは、両方の形態を有します。だから我々が得る：

Q s Q' 
q3 b q4 (q3 initial, q4 accepting) 

と私たちは、この再帰ブランチの底を打っていると我々は定義されている具体的なマシンに基づいて遷移テーブル内の具体的なエントリを生成する、バックステップアップすることができます

Q s Q' 
q5 a q6 (q5 initial, q6 accepting) 

。私たちは、この持っていた：

Q s Q' 
q2 - M3 
M3 - M4 

をそして今、我々は好きなものをM3とM4外観を知っているので、私たちは置き換えることができます：

Q s Q' 
q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 (q2 initial, q6 accepting) 

は、今、私たちは+操作からLHSを行う準備ができています。一番外側の操作は*です。これらをNFAsで処理する方法は次のとおりです。

Q s Q' 
q7 - M5 
M5 - M5 

次の操作、連結を検討します。我々はすでにこれをカバーしているし、我々はこれを取得する知っている：

Q s Q' 
q8 - M6 
M6 - M7 

は、今、私たちはaとbを必要としています。我々は戻って一緒にすべてを置く

Q s Q' 
q9 a q10 

と

Q s Q' 
q11 b q12 

：

Q s Q' 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 (q8 initial, q12 accepting) 

その後、我々はクリーネ閉包の操作を行います。

Q s Q' 
q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q8 initial, q8 and q12 accepting) 

ここでも、我々はこれらがどのように見える知っています

最後に、すべてのルールを1つの大きなトランステーブル：

Q s Q' 

q0 - q2 
q0 - q7 

q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 

q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q0 initial, q6, q8 and q12 accepting) 

これで、任意の正規表現に対してNFAを再帰的に構築することができます。一般的なケースでは、結果として得られるNFAにいくつかの不要な状態がありますが、NFAの最適化は繊細なトピックです。この（または任意の）NFAを使用して、既知のアルゴリズムを使用してDFAに変換し、既知のアルゴリズムを使用して最小化することができます。それから、このパッディングされたNFAよりもはるかに大きいかもしれませんが、おそらく最小限のDFAしか持っていません！