Understanding application of Arden's theorem to find regular expression

Question

I learnt Ardens theorem and its usage as follows:

Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a unique solution that is $R = QP^*$

Using Ardens theorem (source):

Using Arden's theorem to find regular expression
1. For getting the regular expression for the automata we first create equations of the given form for all the states
$q_1 = q_1w_{11} + q_2w_{21 }+ … + q_nw_{n1} + \epsilon$ ($q_1$ is the initial state)
$q_2 = q_1w_{12} + q_2w_{22} + … + q_nw_{n2}$
:
$q_n = q_1w_{1n} + q_2w_{2n} + … + q_nw_{nn}$
where $w_{ij}$ is the regular expression representing the set of labels of edges from $q_i$ to $q_j$ 2. Note: for parallel edges there will be that many expressions for that state in the expression. 4. Solve these equations to get the equation for $q_i$ in terms of $w_{ij}$ and that expression is the required solution, where $q_i$ is a final state. 3. Ignore trap states while doing above.

I feel $R=Q+RP$ is equivalent to left linear grammar production $R\rightarrow Q | RP$. But I dont know whether I should call $R=Q+RP$ as left linear grammar. But I understand the theorem also holds for right linear grammar (if you allow me to call it that for convenience) production also; i.e.

$R = Q + PR$ has a unique solution $R = QP^*$

Now I have came across two problems, one which uses right linear grammar, other using left linear grammar.

Problem 1 (Using right linear grammar)
Given:
$\Sigma=\{0,1\}$
$X_0=1X_1$
$X_1=0X_1+1X_2$
$X_2=0X_1+\{\lambda\}$
Give the regular expression representing strings in $X_0$.

Solution 1 using Arden's theorem
$X_1=0X_1+1X_2$
$=0X_1+1(0X_1+\lambda)$
$=0X_1+10X_1+1)$
$=(0+10)X_1+1$
$=(0+10)^*1$ (By Arden's theorem)
$X_0=1X_1$
$=1(0+10)^*1$

Solution 2 by drawing automaton
The automaton can be drawn for given equations as follows:

Regular expression for automaton = answer for the given question $=1(0+10)^*1$

---

Problem 2 (using left linear grammar)
Given:
$\Sigma = \{a,b\}$
$X_0=\epsilon + X_0b$
$X_1=X_0a+X_1b+X_2a+X_3a$
$X_2=X_1a+X_2b+X_3b$
Give regular expression for $X_1\cup X_2$

Solution 1 using Arden's theorem
was not given. So I tried to solve myself. First thing I noticed was that I can fully ignore $X_3$ as its equation was not given. I felt its unreachable state which is somewhat backed by solution given below using automaton (but the steps listed above in application of Arden's theorem only talks about trap state in last step, not unreachable state). But I was not able to solve this using Ardens theorem. So, I analysed the equations. In problem 1, $X_2$ is defined in terms of $X_1$. So we were able to put value of $X_2$ in $X_1$. So we were able to get $X_1$ in terms $X_1$ itself which can be reduced to regular expression using Arden's theorem. That doesn't seem to be the case here, as $X_1$ and $X_2$ are defined in terms of each other.

Solution 2 by drawing automaton
The automaton can be drawn for given equations as follows:

Regular expression for automaton = answer for the given question $=b^*a(a+b)^*$

After going through all these, I have bunch of related questions:

1. Which is the initial state?
   "Using Arden's theorem" section says $q_1$ is initial state and $q_1$ has $\epsilon$. So I feel that the variable which has $\epsilon$ added (ORed) to its equation, is starting state.

2. Which is final state?
   Again "Using Arden's theorem" section says we solve for final state. So I suppose the variable for which we have been asked to solve for in the question, turns out to be the final state. Right? (Problem 1 asks to solve for $X_0$, so the solution 1 for problem 1 solves for $X_0$. Problem 2 asks to solve for $X_1\cup X_2$ and in solution 2 of problem 2, $X_1$ and $X_2$ are depicted as final state.)

3. How do I solve problem 2 which using Arden's theorem?
   Problem 2 asks for solution of union $X_1\cup X_2$. What does it means to solve for union of two variables in the context of Arden's theorem? How can I solve it?

4. Is it right to draw automatons the way they have drawn?
   In problem 1, each equation gives transition (in automaton) going out of the state corresponding to the variable on LHS. In problem 2, each equation gives transition (in automaton) coming inside the state corresponding to the variable on LHS. Is this right to do?

5. Which one is trap state (and unreachable)?
   Is it correct to interpret variable for which no equation is given as a trap state? For example in problem 2 (left linear), equation is given for $X_3$, so it turned out to be unreachable state. But if such variable (for which no equation is given) was given in problem 1 (right linear), I guess, it would have been trap state (no transition emitting out from the state corresponding to that variable). Can we ignore both?

Answer 1

Well, all doubts rose because standard reference (Ullman and Peter Linz) books I have, do not speak anything about Arden's theorem. I learnt it from some online resources earlier.

I have another book from local publication which have this topic (poor theory but good number of examples). I should have checked it earlier. But being local publication, I barely check it. Anyways, trying to answer my own questions:

1. I was correct with the fact that the variable having $+\epsilon$ in its equation corresponds to the initial state.
2. I was correct with the fact that the variables for which the question asks to solve is indeed the final state.
3. I will give the full solution after answering 5th question
4. I dont feel drawing automaton in the way they have done is wrong. They makes sense, does conform with regular expressions formed by Arden's method. Its just that finding right linear examples in some sources and left linear examples in other sources confused me. No source explained me both. So was anxious whats correct or both correct. Turns out that both are just fine.
5. The point I made about trap state and unreachable state makes sense to me now and feels correct.

Answer to question 3 - solving problem 2

$X_0=\epsilon + X_0b$ ...equation(1)
$X_1=X_0a+X_1b+X_2a+X_3a$ ...equation(2)
$X_2=X_1a+X_2b+X_3b$ ...equation(3)

$X_3$ is unreachable. So deleting it from both equation (2) and (3).

$X_1=X_0a+X_1b+X_2a$ ...equation(4)
$X_2=X_1a+X_2b$ ...equation(5)

Applying Arden's theorem to equation(1), we get

$X_0=\epsilon b^*=b^*$ ...equation(6)

Substituting value of $X_0$ from equation(6) in equation (4), we get

$X_1=b^*a+X_1b+X_2a$ ...equation(7)

Applying Arden's theorem to equation(3), we get

$X_2=X_1ab^*$ ...equation(8)

Putting value of $X_2$ from equation(8) to equation(7), we get,

$X_1=b^*a+X_1b+X_1ab^*a$
$X_1=b^*a+X_1(b+ab^*a)$
$X_1=b^*a(b+ab^*a)^*$ ...equation(9)

Applying Arden's theorem to equation(2), we get

$X_1=(b^*a+X_2a)b^*$ ...equation(10)

Putting equation(10) in equation(5),

$X_2=(b^*a+X_2a)b^*a+X_2b$
$=b^*ab^*a+X_2ab^*a+X_2b$
$=b^*ab^*a+X_2(ab^*a+b)$

Applying Ardent's theorem, we get

$X_2=b^*ab^*a(ab^*a+b)^*$ ...equation(11)

Desired solution $=X_1+X_2$

Applying newly found values from equation(9) and (11), we get,

$X_1+X_2=b^*a(b+ab^*a)^*+b^*ab^*a(ab^*a+b)^*$

That's it how far I am able to reach. I still need to know if Arden's theorem can reduce this regular expression to $b^*a(a+b)^*$. Or I have to explicitly apply regex identities. If yes, I am unable to do it and reduce that long regular expression to $b^*a(a+b)^*$. Can someone help?

All I have done is to check some more examples from that book (book explained theory poorly but have a lot of examples) by local publication and I have come up with opinions which I feel are correct. Of course I am still a bit hesitant to say I am fully confident about above as I have not checked any reference book explaining the same in detail. Will love if anyone points out any mistake.