Contenus

Toggle## 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_{2} accepted by state 2 is equal to: L_{2} = L_{1}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_{1} in the second equation by its value then L_{2} 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_{2} accepted by state 2 is equal to: L_{2} = aL_{1}+ aL_{3}+ ε (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_{3} and L_{4} in the first two equations then L_{2} 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.