# Convert finite automata to regular expression

I am trying find the regular expression that describes the finite automata in the image below.

Given the following finite automata

which of the following regular expressions describes the same language as the automaton.

• (ab)+c*d+
• a+b+c*d+
• a(ba)*bc*dd*
• [ab]+c*d+
• a(ba)*bc+d?d+
• (ab)+c+d*

I tried converting it to a regular expression and I got (ab)*ac*dd*, which is not among any of the options. Could someone help me select the correct answers?

• I got (ab)*ac*dd* how did you get the a between b and d? (dd* is fine, depending on context/definition, d+ is a shorter version thereof.) Oct 22 '20 at 16:20

You have an error in your regular expression. The correct one is $$(ab)^*ab c^*dd^*$$ (notice that after reading $$(ab)^*$$ you are in state $$A$$ and that the edge from $$B$$ to $$C$$ is labelled $$b$$).
This can be rewritten as $$(ab)^+ c^*d^+$$ since $$(ab)^*ab = (ab)^+$$ and $$dd^* = d^+$$.
Another equivalent expressions is $$a(ba)^*bc^*dd^*$$ since $$(ab)^+ = a(ba)^*b$$.
• No, sorry. What I used is just the definition of "plus". If $E$ is a regular expression then $E^+$ is defined as $EE^*$ (or equivalently $E^*E$). The equality $(ab)^+ = a(ba)^*b$ follows from the fact that both expression correspond to words with $k \in {2,4,6,\dots}$ alternations of "a" and "b". Therefore $(ab)^+ = ab(ab)^* = (ab)^*ab = a(ba)^*b$. Oct 22 '20 at 16:13