2
$\begingroup$

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

enter image description here

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

enter image description here

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:

enter image description here

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you very much. I understood the removal of state III. As you told after removing states III, it is just rinse and repeat. But can you please provide the removal of remaining states? I mean removal of states I and IV? $\endgroup$ – Kaushal28 Aug 6 '16 at 6:17
  • $\begingroup$ @Kaushal28 This would get rather lengthy and I'm not sure it'd add much value to the answer. Is there something specific that you still would like to have explained for removing those states? $\endgroup$ – ComicSansMS Aug 6 '16 at 6:20
  • $\begingroup$ Yes, I understood the removal of state III, but again stuck in removal of state IV and I. @ComicSansMS $\endgroup$ – Kaushal28 Aug 6 '16 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.