Stuck in converting finite automata to its corresponding regular expression

Question

I'm trying to convert the following finite automata (DFA) to its corresponding regular expression using state elimination algorithm.

For this I'm following this link. The answer of that question has following example.

But in this sample automata, there is no state between the two looping transitions. For example there is no state between transition q to r and back r to q. But in my question, there is three such cases as mentioned in the above 1st diagram. For example there is a state IV between the transition III to V and back V to III, via a. For another example, there is three intermediate states between transition I to V and back V to I via b.

I've tried to search such case on INTERNET, but can't found such issue. I've tried to attempt this question and could eliminated the II state, as following:

I'm stuck in eliminating state I, III and IV. Suppose I remove state III, than where should the transition from V to III via a can be placed? If I eliminate state IV, what will happen to transition IV to I?

Is there any general method for this type of cases? Any help will be appreciated.

Thank you very much in advance!

Answer 1

Let's merge IV.

We have three edge transitions to consider:

• IV to I, consuming a b (1)
• IV to V, consuming an a (2)
• III to IV, consuming a b (3)

The only way I can enter state IV is via III (3). Hence, any state that can be reached from IV can also be reached from III.

Let's now look at the path III -> IV -> I, which is the concatenation of (3) and (1). Let's forget about states for a second and simply look at paths and the consumed symbols. There exists a path ((3),(1)) that allows us to get from III to I by consuming a bb.

Due to this fact, we can just add an edge III to I consuming a bb without changing the accepted language of the automaton. It's just a shortcut for the existing path. Once we added the edge, the original path is redundant. If I'm sitting at III, instead of walking the path (3),(1), I can just take the shortcut.

Once I have made all the paths redundant that pass through a state, the state itself becomes redundant and I can remove it along with all its edges.

We can apply the same logic to III -> IV -> V. This introduces a shortcut edge III to V consuming a ba.

With those two in place, we have covered all paths that pass through IV. You can easily enumerate all paths by taking the Cartesian product of incident and outgoing edges: I have a certain number of ways of reaching the state, and for each of those I have to consider all the possible ways of exiting the state again.

Now it's just rinse and repeat. Pick a state, enumerate all paths through it, insert shortcut edges that make all paths redundant and then remove the state along with all its edges.

The only thing to watch out for are loops. The answer you linked in your question should give you a good idea how to deal with those.