regex - 如何将正则表达式转换为有限状态机？

Question

让正则表达式；

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

将此表达式转换为有限状态机的规则是什么？

Answer 1

转换通用正则表达式的规则可以在文献中找到（例如 Aho 等人的“编译器：原理、技术和工具”），但是需要大量的努力来编写它。目前，许多开源实现可用于此任务以及有限状态机和传感器上的其他操作，例如 openFST、SFST、Foma 和 HFST（这是三者的通用接口）。它们可作为独立程序、库和通过例如 Python 使用。下面的示例表达式是使用 hfst-xfst 独立程序编译的（有关更多信息，请参见http://hfst.github.io/）。

$ 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]: