# Converting DFA to Regular Expression Using State Removal

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.

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

## 1 Answer

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$$.