# How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states.

I have this difficult DFA i need help converting to RE:

using STATE ELIMINATION

if you could explain ripping state q1 from the DFA it would help a lot

• What is $\{q_0,q_{?}\}$ state? Commented Jul 23, 2018 at 8:59
• The beauty of state elimination - and of all other algorithms to convert a DFA to an RE - is that they are completely mechanical. You could - and some people did - program a computer to execute them. They require no creativity on your part. You just have to follow the algorithm as written. If the algorithm hasn't been presented to you in a way which makes it possible to implement it mechanically, ask your teacher for such a version. And tell them that exercises like the one you are trying to solve currently are best given to a computer rather than to a human being. Commented Jul 24, 2018 at 6:51
• @YuvalFilmus I sympathize. But unfortunately exercises like this are the only way to make some students read the instructions. It might be a first step to wanting to understand why the steps are formulated that way. Sigh. Commented Aug 10, 2019 at 13:08

If we're talking about the same Elimination problem then you should add an accept state and a start state. In addition, I allowed myself to disregard state $q_b$ as it never part of the language.

The start state will replace $q_0$. The accept state will replace $q_9$. Then to your request, we'll do the rest, starting from $q_1$.

From $q_1$ you either have 0 endless times or a 1 in other words, $0^* \cup1$ from $q_1$ to $q_2$.

Let us now rip $q_3$: from $q_2$ to $q_4$ you'll need 01. While from $q_4$ to $q_1$ you'll need 00.

Proceeding to rip $\{q_0, q_2\}$, note this is no more than a name and could just as well be renamed to $q_5$. Thus from $q_2$ to $q_1$ we have: $11*0$

All that's left is to close the circles which are probably cause your trouble: For the fun of it, we'll go by order. Let us rip $q_1$: This means $q_0$ reaches $q_2$ using a concatenation of 0 with the resulting regex of $q_1$ to $q_2$ which is we found and was $0^*1$. Removing $q_1$ then completes the self-cycle of $q_2$ and there would now be an arrow to self: $11^*0$.

Nearly done, remove $q_2$: remove $q_2$ thus connecting $q_0$ to $q_4$ through $0((0^*1)11^*0)^*01$, however, there are also the loops that are created to be taken into account, see the drawing attached: I realized that this is very confusing to read so I've added the following drawing:

I might have missed a character or two, but those are my two cents, also- remember to keep the loops in mind and their final transitions.

P.s. I noticed in the second NFA (yes, NFA as there are $\epsilon$ transitions), I have accidentally forgotten to add the transition itself from $q_2$ to $q_1$, however it is there in the next NFA

• in the final RE, there should be an $\cup$ simple in between the different loops. My apologies. Commented Aug 14, 2018 at 12:38