Next: Deterministic Finite-State Automata Up: Non-Deterministic Finite-State Automata Previous: Kleene's Theorem   Contents

### Converting a NFA to a Regular Expression

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)

Next: Deterministic Finite-State Automata Up: Non-Deterministic Finite-State Automata Previous: Kleene's Theorem   Contents
James Power 2002-11-29