<p>There are several algorithms to perform this task: the "state-elimination method" from Brzozowski and Mc Cluskey, the resolution of a system of linear equation, the method from McNaughton and Yamada, etc.  They are very well described in <a href="http://arxiv.org/abs/1502.03573" rel="noreferrer" title="Automata and rational expressions">Automata and rational expressions</a> by Jacques Sakarovitch.</p>

<p>The state-elimination method in particular is simple to understand.  The key idea is that you are going to build an automaton labeled by rational (aka regular) expressions rather than letters.  First, make sure you have a single initial state and a single final state (you may add fresh states and spontaneous transitions if necessary). Then choose a state s to eliminate, say state 1 in the following picture.</p>

<p><a href="https://i.stack.imgur.com/r4cH9.png" rel="noreferrer"><img src="https://i.stack.imgur.com/r4cH9.png" alt="A simple automaton"></a></p>

<p>Then consider all the couples (p, q) where p is a predecessor (states from which a transition reaches s, 0 in the picture) and q a successor (state 2).  For each such couple (p, q) add a transition from p to q which is labeled by E(p, q) + E(p, s)E(s, s)*E(s, q) where E(p, s) means "the expression that labels the transition from p to s.  Once you treated all the couple (p, q), remove the state s.  In the previous example:</p>

<p><a href="https://i.stack.imgur.com/ZF4fm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ZF4fm.png" alt="An automaton labeled by regexps"></a></p>

<p>Do that until you eliminated all the inner states (i.e., keep the initial state and the final state), and just read the result on the transition from the initial state to the final state (here d+ab*c).</p>

<p>You may toy with this algorithm using <a href="http://vcsn.lrde.epita.fr" rel="noreferrer" title="Vcsn">Vcsn</a>, a tool for rational expressions and automata.  Here is a complete example you may reproduce at <a href="http://vcsn-sandbox.lrde.epita.fr" rel="noreferrer" title="Vcsn Sandbox">Vcsn Sandbox</a>.</p>

<p><a href="https://i.stack.imgur.com/ko9jA.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ko9jA.png" alt="A complete run of the state elimination method"></a></p>
Convert finite state machine to regular expression
<p>Is there a tool (or an algorithm) to convert a <em>finite state machine</em> into a <em>regular expression</em>?</p>

<p>(not the other way around, that would be easy).</p>