Как преобразовать регулярное выражение в конечный автомат?

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