[Solved]: How to convert an NFA with overlapping cycles into a regular expression?

Problem Detail: 

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in this case:

^[source]

The overlapping cycles make it hard to see what this automaton accepts (in terms of regular expressions). Is there a trick?

Asked By : zell

Answered By : Raphael

Rather than "reading off" you should employ one of several canoncial methods to do this. By far the nicest I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma (a needed result) is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

In short: For every state $q_i$, create the equation

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q_i \overset{a}{\to} q_j$ means there is a transition from $q_i$ to $q_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

Solving it (using Arden's Lemma) yields one regular expression $Q_i$ for every state that describes exactly those words that can be accepted starting in $q_i$; therefore $Q_0$ (if $q_0$ is the initial state) is the desired expression.

Application to the given automaton is left as an exercise; a complete example is included in above linked document.

^{See also here where I posted a similar answer.}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/689