自动机到正则表达式

Question

我有这个简单的自动机：

然后我写我的系统:

L0 = aL0 + bL1

L1 = bL0 + aL1 + Ɛ

使用 Arden 定理我可以简化我的表达式：

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*

这个正则表达式似乎是正确的。