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 ?

  • $\begingroup$ Every regular language can be described by infinitely many regular expressions. $\endgroup$ Nov 26 '19 at 9:04
  • 1
    $\begingroup$ 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 $\endgroup$ Nov 27 '19 at 11:57

The two regular expressions describe the same language.

enter image description here


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.