自动机正则表达式（并运算场景）：A₁∪A₂对应正则是否等价于R₁+R₂？

结论 #

从A₃推导得到的正则表达式与R₃ = b*ab*a(a+b)* + a*ba*b(a+b)*完全等价。

等价性验证依据 #

• 自动机并运算A₃ = A₁ ∪ A₂的核心语义是：A₃接受的字符串集合，是A₁接受的字符串集合与A₂接受的字符串集合的并集，即所有满足「至少包含2个a」或者「至少包含2个b」的字符串。
• 正则表达式中+操作符的语义同样是匹配范围的并集：R₁ + R₂可匹配的所有字符串，恰好就是能被R₁匹配的串、或能被R₂匹配的串。
• 已知A₁对应的正则为R₁、A₂对应的正则为R₂，因此二者的并运算结果不存在语义差异，对应正则完全等价。

内容的提问来源于stack exchange，提问作者karalis1