Arden’s rule

It is important to note that there are two symmetrical versions of Arden’s rule:

automate2

Depending on which version you use the method to generate the equations is slightly different.

From the right

Take the following automaton:

langage33

The construction of the equations is 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 = L1a. A word w ∈ Li if and only if he
there exists a computation of the automaton on w starting from the initial state and arriving in the state i (attention the version is not the same on a left version).

We have the following system:

langage34

By substituting L1 in the second equation by its value then L2 in the third and fourth equations we obtain:

langage35

The Arden’s rule is applied to the last two equations:

langage36

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*

From the left

Take the following automaton:

langage37

The construction of the equations is 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 ∈ L if and only if there exists a computation of the automaton on w starting from the state i and arriving in a final state (attention if one used the other version the definition would be different).

We have the following system:

langage38

Substituting L3 and L4 in the first two equations and then L2 in the first equation we obtain:

langage39

Finally, applying Arden’s rule (left version) to the first equation gives L1 = (a + bba + bbab) * (bb + ε). Here we have the language recognized from the initial state, therefore from the automaton.