RegEx для преобразования путевого графа

Question

В значительной степени нас просят найти регулярное выражение для DFA, как показано в ссылке, прикрепленной выше. То, что я получил, - это путь от s0 до s2, который я считаю (a (b (ab) ) и от s0 до s4, который я считаю b (a (ba) ). Но я ' я не уверен, как включить путь от s1 до s3.

Я попытался взглянуть на эту ссылку , чтобы попытаться понять, как они преобразовали свой DFA в регулярное выражение, но я все еще потерялся.

Answer 1

Спасибо за смешную проблему!

Нам нужно разбить его на части:

(a{s1 to end})|(b{s3 to end})

{s1 to end}:

{s1 to s1}*{s1 to end without coming back to s1}

{от s1 до s1}:

(a(ab)*b)|(ba)

{s1 до конца, не возвращаясь к s1}:

b|(aa(ba)*)

{s3 до конца}:

{s3 to s3}*{s3 to end without coming back to s3}

{от s3 до s3}:

(b(ba)*a)|(ab)

{s3 до конца, не возвращаясь к s3}:

a|(bb(ab)*)

Тогда мы можем собрать все это вместе:

(a{s1 to s1}*{s1 to end without coming back to s1})|(b{s3 to s3}*{s3 to end without coming back to s3})

что в итоге дает:

(a((a(ab)*b)|(ba))*(b|(aa(ba)*)))|(b((b(ba)*a)|(ab))*(a|(bb(ab)*)))

РЕДАКТИРОВАТЬ: исправлена ​​ошибка, которая проскользнула в последнее выражение