I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation X = A⋅X ∪ B where X, A, B are sets of strings. Moreover, if the set A does not contain the empty word, then this solution is unique.
So I write the regular expression $r = rs + t$ and I have to prove that $r = s^{\ast}t$ is a solution
First i intend to prove that is a solution by proving that $s^{\ast}t = ss^{\ast}t + t$
I proved that $L(s^{\ast}t)\subseteq L(ss^{\ast}t) \cup L(t)$
Unfortunately I'm stuck proving $L(ss^{\ast}t) \cup L(t)\subseteq L(s^{\ast}t) $
If I try proving $L(ss^{\ast}t)\subseteq L(s^{\ast}t) $ by induction I have the basis as $L(st)\subseteq L(t)$ but this isn't true...
What's the correct way to prove this?
I would work directly with the sets. Suppose that $w\in A^*B$. Then either $w\in B$, or there is are a positive integer $n$ and words $a_1,\ldots,a_n\in A$ and $b\in B$ such that $w=a_1\ldots a_nb$. In the first case $w\in B\subseteq AA^*B\cup B$, and in the second case $a_2\ldots a_n\in A^*$, so $w\in AA^*B\subseteq AA^*B\cup B$. Thus, $A^*B\subseteq AA^*B\cup B$. In similar fashion you can show that $AA^*B\cup B\subseteq A^*B$ and conclude that $X=A^*B$ is indeed a solution to the equation $X=AX\cup B$.
As a pointer for the last part of the question, note that for any set $A$ of strings, $A^*=(A\setminus\{\lambda\})^*$, where $\lambda$ is the empty word.