Search code examples
regular-languageautomatafinite-automataautomata-theory

Automata to regular expression

I have this simple automata :

enter image description here

Then I write my system :

L0 = aL0 + bL1

L1 = bL0 + aL1 + Ɛ

Using Arden's Theorem I can simplify my expression :

L0 = a*bL1

L1 = bL0 + aL1 + Ɛ

Then :

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

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

L1 = b(a*b+a)*

It seems to be incorrect but I don't understand why, can someone explain me where I'm wrong?

Solution

  • Your problem is that L0 and L1 represent the languages of strings that lead to L0 and L1, not the languages of strings that lead from L0 and L1 to an accepting state. Therefore, the empty string is not equivalent to L1, the accepting state, but to L0, the initial state. Therefore,

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

    Then

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

    Next

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

    This regular expression does appear to be correct.