Solving by Arden's lemma

Lemma of Arden

It is important to note that there are two symmetrical versions of Arden's lemma. Depending on the version you use, the method to generate the equations is slightly different.

Right version

Consider the following automaton:

The construction of the equations is done as follows: the language recognized by a state is equal to the language followed by the transition symbol of its predecessors. For example, the language L₂ accepted by state 2 is equal to: L₂ = L₁To. A word w ∈ L_i if and only if he
exists a calculation of the automaton on w starting from the initial state and arriving in the state i (attention the version is not the same one on a left version).

We have the following system of equation:

By substituting L₁ in the second equation by its value then L₂ in the third and fourth equations we get:

We apply the right Arden lemma to the last two equations:

The language recognized by the automaton is the set of languages recognized by its terminal states, which in this example gives: ab (a + b) * + (b + aa) a *

Left version

Consider the following automaton:

The construction of the equations is done as follows: the language recognized by a state is equal to the language preceded by the transition symbol of its successors. For example, the language L₂ accepted by state 2 is equal to: L₂ = aL₁+ aL₃+ ε (because it is a terminal state). A word w ∈ L_i if and only if he
exists a computation of the automaton on w starting from state i and arriving in a final state (be careful if we used the other version of the lemma, the definition would be different).

We have the following system of equations:

By substituting L₃ and L₄ in the first two equations then L₂ in the first equation we get:

Finally, by applying Arden's lemma (left version) to the first equation we
obtains: L1 = (a + bba + bbab) ∗ (bb + ε). Here we have the language recognized from the initial state, therefore from the automaton.