正規表現を有限状態マシンに変換するには？

Question

正規表現をしましょう。

r = (a*|(ab)*)b* 

この式を有限状態マシンに変換するルールは何ですか？

Answer 1

一般的な正規表現を変換するための規則は、文献（例：Aho et al。 "Compilers：Principles、Techniques、and Tools"）にありますが、プログラミングにはかなりの労力が必要です。現在、多くのオープンソースの実装が、このタスクのために利用可能であり、有限状態マシンおよびトランスデューサに関する他のオペレーションが利用可能である。 openFST、SFST、Foma、およびHFST（これらの3つの共通インタフェース）です。スタンドアローンプログラム、ライブラリ、 Python。下の例の式は、hfst-xfstスタンドアロンプ​​ログラムを使用してコンパイルされます（詳細は、http://hfst.github.io/を参照してください）。 Googleで

$ hfst-xfst 
hfst[0]: regex [a*|[a b]*]b* ; 
? bytes. 6 states, 10 arcs, ? paths 
hfst[1]: print net 
Sfs0: b -> fs1, a -> fs2. 
fs1: b -> fs1. 
fs2: b -> fs3, a -> fs4. 
fs3: b -> fs1, a -> s5. 
fs4: b -> fs1, a -> fs4. 
s5: b -> fs3. 
hfst[1]: