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

Question

Пусть регулярное выражение;

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

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

Answer 1

Правила преобразования общих регулярных выражений можно найти в литературе (например, Ахо и др. "Компиляторы: принципы, методы и инструменты"), но для его программирования требуется немало усилий. В настоящее время доступно много реализаций с открытым исходным кодом для этой задачи и других операций на машинах и преобразователях с конечным числом состояний, например 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]: 

Answer 2

Данное регулярное выражение

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

Данное регулярное выражение можно разбить на части и снова объединить вместе, чтобы упростить разработку DFA. Разобьем регулярное выражение на a*, ab, (ab), b, a+b, a+(( ab )), (а |(аб) )б

Теперь a* можно превратить в конечные автоматы как a*

Теперь ab можно сделать как

аб

b* можно сделать как b*

Соединяя оба ab и b* в один автомат, мы получаем (ab)* как (ab)*

Теперь a+b как a+b Теперь a+b и (ab)* можно объединить, поместив (ab)* вместо b в a+b, тогда мы получим a+((ab))a+((ab)*) Теперь a+((ab) ) и b* можно соединить с помощью метода ab и получить требуемый результирующий автомат с конечным числом состояний. Результирующее преобразованное (a*|(ab)<em>)b</em>

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

1. Разделите выражение на части, чтобы их было легче понять, и добавьте их. 2. Создайте конечные автоматы Finte для этих частичных выражений. 3. Соедините эти частичные выражения одно за другим. 4. Затем мы получаем результирующий NFA.5. Если мы хотим получить DFA, то с помощью метода ϵ-замыкания преобразуем NFA в эквивалентный DFA.