How to convert an NFA with overlapping cycles into a regular expression?

Question

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?

Answer 1

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.}

Answer 2

If there was just a chain of states with no loop, would you know what to do?

If there was a simple loop without this overlapping branching, would you know what to do?

(If the answer is “no”, think about these cases first.)

Now, the idea is to transform the automaton progressively to put it in a form where you can spot those patterns: chains, loops, and diverging paths that reconverge in the end (leading to alternation). At every step of the transformation, take care that the transformed automaton still recognizes the same language.

Keep in mind that this is a non-deterministic automaton. The one you posted happens to be deterministic, but it doesn't have to stay that way when you transform it.

Since the sticky point is that $q_2$ can be reached from two different points, split it in two. Keep $q_1 \xrightarrow{f} q_2 \xrightarrow{g} q_3$, remove the transition from $q_4$ to $q_2$ and add instead a new state $q_5$ with transitions $q_4 \xrightarrow{j} q_5 \xrightarrow{g} q_3$. Now you should be able to spot a pattern.

If you still have trouble at this point, notice that the loop involving $q_3,q_4,q_5$ corresponds to a simple regular expression. When you get to $q_3$, you can make as many runs around this loop as you like. In some sense (which can be made technical), you can replace the state $q_3$ by the regular expression $(hjg)^*$.

Take care to check which states are final. It can help to not worry about this at first and make one big loop, then duplicate parts that terminate partway through the loop.

This is not necessarily the most efficient technique or the one that generates the simplest regular expression, but it's simple.

Answer 3