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:
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.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.)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?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?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?