0
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ What is $\{q_0,q_{?}\}$ state? $\endgroup$ – Dmitri Urbanowicz Jul 23 '18 at 8:59
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 24 '18 at 6:51
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Aug 10 at 13:08
0
$\begingroup$

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:

Stages of the stripping process

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

$\endgroup$
  • $\begingroup$ in the final RE, there should be an $\cup$ simple in between the different loops. My apologies. $\endgroup$ – Reckless Engineer Aug 14 '18 at 12:38

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.