# Different application of Arden's theorem leads to different answers

So, I have to solve for the following set of equations

$$q_1$$ = $$q_1$$a + $$q_2$$b + $$\epsilon$$

$$q_2$$ = $$q_1$$a + $$q_2$$b + $$q_3$$a

$$q_3$$ = $$q_2$$a

There are two ways to do this.

I did this

$$q_1$$ = $$q_2$$b + $$\epsilon$$ + $$q_1$$a

$$q_1$$ = ($$q_2$$b + $$\epsilon$$)a* Applying Arden's theorem

Now substituting in $$q_2$$ the values of $$q_1$$ and $$q_3$$

$$q_2$$ = $$q_2$$ba*a + a*a + $$q_2$$b + $$q_2$$aa

$$q_2$$ = a*a + $$q_2$$(ba*a+b+aa)

$$q_2$$ = a*a(ba*a+b+aa)* Applying Arden's theorem

$$q_2$$ = a*a(ba*+aa)*

Now substituting in $$q_3$$, the answer should be

$$q_3$$ = a*a(ba*+aa)*a

However, the correct answer is

(a + a(b+aa)*b)*a(b+aa)*a

which can be obtained by first substituting $$q_3$$ in $$q_2$$, and then substituting $$q_2$$ in $$q_1$$, and finally solving $$q_2$$, $$q_3$$ from the obtained regular expression for $$q_1$$.

Can someone tell where I have gone wrong in the above method, or am I applying ardens theorem in the wrong way ?

• Every regular language can be described by infinitely many regular expressions. – Yuval Filmus Nov 26 '19 at 9:04
• You stumbled across something really interesting: The ordering in which you eliminate the q's can have a large effect on the size of the resulting regular expressions. See e.g. here for more background: arxiv.org/abs/1008.1656 – Hermann Gruber Nov 27 '19 at 11:57

## 1 Answer

The two regular expressions describe the same language.