1

How do you do convert an ɛ-NFA to a regular expression?

Take for example this ɛ-NFA in which there's an ɛ transition from the final state q2 to the initial state q0:

Inserted figure that shows the ɛ-NFA

I first combine eliminate q1 and get the regular expression $ab^*b(ab^*b)^*$:

inserted figure that shows the ɛ-NFA with q1 eliminated

How do I get from here to a regular expression?

Am I done now and is the regular expression simply $ab^*b(ab^*b)^*$ or should I eliminate the ɛ transition as well to get a correct regular expression?

mvw
  • 34,562
Seno
  • 11

1 Answers1

1

Let us assume the lower branch is given by $r$ then the whole automaton should be $$ r^+ $$ which is short for $$ r^+ = r(r^*) = r^*r $$ I am not sure about the regexp for the lower branch.

It could be $$ a(b^*|(ba)^*)b $$

so we would end up with $$ (a(b^*|(ba)^*)b)^+ $$

mvw
  • 34,562
  • To accept a word you have to finish at $q_2$. So the lower branch has to be traversed once. The $\epsilon$ transition allows to go back into the initial state. So $ab$ matches via $q_0 a q_1 b q_2$ and $abab$ via $q_0 a q_1 b q_2 \epsilon q_0 a q_1 b q_2$. But also $ababbb$ via $q_0 a q_1 b q_2 \epsilon q_0 a q_1 b q_1 b q_1 b q_2$, where $r$ first matches $ab$ and then $abbb$. – mvw Mar 18 '18 at 14:41