regex - 用于转换路径图的正则表达式

Question

几乎我们被要求为 DFA 找到一个正则表达式，如上面的链接所示。我得到的是从 s0 到 s2 的路径，我认为是 (a(b(ab) ) 和从 s0 到 s4 的路径，我认为是 b(a(ba) )。但我不知道如何包括从 s1 到 s3 的路径。

我试着看一下这个链接，试图了解他们如何将他们的 DFA 转换为正则表达式，但我仍然迷路了。

标签： regexregex-negationregex-lookaroundsregular-languagedfa

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 to end} 是：

{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)*)))

编辑：修复了滑入最后一个表达式的错误