Earlier, I asked a question on here asking for help with the conversion of a transition-graph of a finite automaton into a regular expression:
Understanding (and forming) the regular expression of this finite automaton
Thanks to the user Patrick87, I was able to find the help I was looking for. I also read the following link that he mentioned in his answer :
http://krchowdhary.com/toc/dfa-to-reg-exp.pdf
which explains three algorithmic methods to find regular expressions. Intuitively, I was attracted towards the Brzozowski Algebraic Method and tried to solve the FA that I had asked for help on in the previous post which is mentioned at the top.
The following are the characteristic equations that I have made for the FA. Please tell me and correct me if I am wrong and point me in the right direction!
R1 = bR2 + aR3
R2 = aR2 + bR4
R3 = aR3 + bR2 + λ
R4 = aR4 + bR3
Are these correct? If yes, then how how do I go about with the substitutions as every Ri will be in terms of Rj where i≠j.
Please help :D
I'll take a stab at this... We first reduce each equation so that we don't have any Ri's equal to expressions containing themselves...
R1 = bR2 + aR3
R2 = a*bR4
R3 = a*bR2 + a*
R4 = a*bR3
Now for the substitutions... first eliminate R4
R2 = a*ba*bR3
Now we get rid of R2
R1 = ba*ba*bR3 + aR3
R3 = a*ba*ba*bR3 + a*
We don't want R3 on its own RHS...
R3 = (a*ba*ba*b)*a*
Now eliminate R3
R1 = ba*ba*b(a*ba*ba*b)*a* + a(a*ba*ba*b)*a*
This looks right, and as such we can transform it to yours. You should try this exercise.