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

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