The last theorem actually yields an algorithm for converting a NFA to
a regular expression. The proof was by induction; we can transform
this into a recursive function where the recursion is based on an
integer argument.

We note that the induction step tells us that to calculate the language for any , it will either be:

- -
- the language , or
- -
- the language .

If we represent this ``or'' by the union operation, we then have a
recursive definition of in terms of languages of the form
.

The base case is where . As we have seen in the proof of
Kleene's theorem, these machine components correspond to one-step
transitions in the FSA, and the equivalent regular expressions are
thus just the symbols which cause those transitions.

Based on this we can define function `L,` which takes three numbers as
arguments and returns a regular expression, as follows:

`regular-expression L(int I, int J, int K)`

`{`

`if (K==1)`

`return`

there is an `` transition between states and`else`

`return L(p,q,K-1) | (L(p,K-1,K-1).L(K-1,K-1,K-1)*.L(K-1,q,K-1));`

`}`

Given any FSA with states altogether, where is the start state
and is the final state, we convert it to a regular expression by
calling the function `L(S,F,N+1)`