1
$\begingroup$

I'm trying to convert the following NFA to a regular expression.

I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been working at it for quite a while. Can anyone tell me where I went wrong? And if it happens to be correct, can you tell me why?

Thanks a lot in advance.

$\endgroup$
3
  • $\begingroup$ How does the NFA in the 1st image relate to the top-left NFA in the 2nd image? $\endgroup$
    – frabala
    Mar 6, 2020 at 15:35
  • $\begingroup$ @frabala, the top left NFA is the GNFA corresponding to the 1st image (with the exclusion of the phi transitions. $\endgroup$
    – Pwned1760
    Mar 7, 2020 at 2:46
  • $\begingroup$ In the elimination of (1,2), you've lost the transition from (2,3) on a. $\endgroup$
    – rici
    Mar 7, 2020 at 3:56

1 Answer 1

Reset to default
0
$\begingroup$

Think of it this way. You can reach 2 from 1 in two ways

  • $1\rightarrow 2$
  • $1\rightarrow 3 \rightarrow 2$

Then from 2, you can move to 1 by $2\rightarrow 1$. From there again, move to 2 from 1 in the above two ways. So this NFA can be expressed as an RE as follows:

$$RE = (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2) \cdot [(2\rightarrow 1)\cdot (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2)] ^*$$

Now its just the matter of finding the REs for $1\rightarrow 2$, $1\rightarrow 3 \rightarrow 2$ and $2 \rightarrow 1$.

$\endgroup$

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.