How can an NFA be converted into a regular expression using GNFA?

[Dragonfall]

Is there an algorithm for converting DFA (or NFA) into regular expressions?

 

[gunch]

Yes, while I have no idea whether it is the most efficient (probably not), one of the easiest ways is to convert the DFA or NFA into a GNFA (generalized nondeterministic finite automaton) and start collapsing its states till only one transition is left, and then take that as the regular expression.

A GNFA is simply a NFA that accepts regular expressions on arrows instead of just symbols. The general idea is as follows:
1. Take any NFA, and add two states we call start and end. Add an epsilon-arrow from start to the previous start state, and add an epsilon-arrow from all previous final states to the end state. Now start is the only start state, and end is the only end state.
2. If start and end are the only states then we take the regular expression on the arrow between them and are done, if not we go to 3.
3. We pick a state Q that is not start or end. Let R be the arrow from Q to itself. Now from every state A that has an arrow C to Q, for every state B that has an arrow D from Q we add an arrow from A to B with the label CR*D.
4. We remove the state Q and all arrows to it, since we have constructed replacements.
5. If there exist two states A and B such that there are several arrow from A to B, then we reduce them to one by taking the union of all the arrows.
6. Go to step 2.