Finding regular expressions.

Question

I have the following DFA:

I want to find the language of this DFA with the help of regular expressions.

So this my attempt:

I will use the Formula L(G) = $\bigcup_{j : s_j \in E} R_{1,j}^n$.

I get L(G) = $R_{1,3}^4 = R_{1,3}^3 \cup R_{1,4}^3(R_{4,4}^3)^{*}R_{4,3}^3$. So all I need to find are these 4 regular expressions.

my idea for $R_{1,3}^3$ and $R_{4,3}^3$:

$R_{1,3}^3 = (0^{*}10)(10^{*}10)^{*}$

$R_{4,3}^3 = (10^{*}10)(10^{*}10)^{*}$

am I right?

my problem is $R_{1,4}^3$.

So first I would say that we start with $0^{*}1$. Now I need to work with this symbol: | ("or"). I could take $1$ or $0$ at this point. If I take $1$. I would have $0^{*}11$. If I take $0$ I would have $0^{*}10$ but I'm not in $s_4$ I'm in $s_3$. At this point I have use | ("or") again. If I take $0$ I would have $0^{*}100$. If I take $1$ I would be in a circle. I don't know how to handle this circle. Can you help me out?

$R_{1,4}^3 = 0^{*}11|0^{*}100| $circle case, where I need help.

Answer 1

One can easily eliminate s4 and keep only the transitions

s1:  0*1 --> s2
s2:  10*1 --> s1
s2:  0 --> s3
s3:  0*1 --> s1

One sees that all the paths from s1 to s2 that don't traverse s3 have the form 0*1(10*10*1)*. Hence the paths from s1 to s3 without repetition of s3 are W = 0*1(10*10*1)*0. It follows that all the paths from s1 to s3 have the form W(0*1W)*, that is to say

0*1(10*10*1)*0(0*10*1(10*10*1)*0)*

If you have a link to a reference to the notations and formula that you are using, it should be feasable to rewrite the above argument in term of these notations.