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*

この正規表現は正しいようです。