Arden Lemma
It is important to note that there are two symmetric versions of Arden's lemma. Depending on the version you use, the method for generating 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 L2 accepted by state 2 is equal to: L2 = L1To. A word w ∈ Li if and only if he
there is a calculation of the automaton on w starting from the initial state and arriving in state i (note the version is not the same on a left version).
We have the following system of equations:
By substituting L1 in the second equation by its value then L2 in the third and fourth equations we get:
We apply Arden's right lemma to the last two equations:
The language recognized by the automaton is the set of languages recognized by its terminal states, which gives in this example: 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 L2 accepted by state 2 is equal to: L2 = aL1+ aL3+ε (because it is a terminal state). A word w ∈ Li 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 L3 and L4 in the first two equations then L2 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 + ε). We have here the language recognized from the initial state, therefore from the automaton.