regular-language - 自动机到正则表达式

Question

我有这个简单的自动机:

然后我编写我的系统:

L0 = aL0 + bL1

L1 = bL0 + aL1 + Ɛ

使用雅顿定理我可以简化我的表达式:

L0 = a*bL1

L1 = bL0 + aL1 + Ɛ

然后:

L1 = b(a*bL1) + aL1 + Ɛ

L1 = b(a*b+a)L1 + Ɛ

L1 = b(a*b+a)*

这似乎是不正确的，但我不明白为什么，有人可以解释我哪里错了吗？

Answer 1

您的问题是 L0 和 L1 代表导致 L0 和 L1 的字符串语言，而不是从 L0 和 L1 导致接受状态的字符串语言。因此，空串并不相当于L1(接受状态)，而是相当于L0(初始状态)。因此，

L0 = aL0 + bL1 + Ɛ
L1 = bL0 + aL1

然后

L0 = a*(bL1 + Ɛ)
L1 = bL0 + aL1

下一步

L0 = a*(bL1 + Ɛ)
L1 = ba*(bL1 + Ɛ) + aL1
   = ba*bL1 + ba* + aL1
   = (ba*b + a)L1 + ba*
   = (ba*b + a)*ba*

这个正则表达式看起来确实是正确的。