Regular expressions: Show that A*B is the solution of X = AX + B I'm currently working on the following problem for my computer theory class. It goes as follows:

Let $A$ and $B$ be regular expressions. Show then that $A^*B$ is the solution
  of $X = AX + B$

Am I supposed to let $X = A^*B$? If so then 
$A^*B = A(A^*B) + B$
I can understand that  $A(A^*B)$ could be reduced to $A^*B$ but what happens with the "${}+ B$" part of the expression? I've read up on Kleene algebra and found an axiom that seems relevant in which 

$b + ax ≤ x → a^∗b ≤ x$

but I'm not actually sure if it applies. 
 A: In order to show that $A^*B$ is "the" solution to $X=AX+B$ you have to show that (1) $A^*B$ is "a" solution to $X=AX+B$, and (2) if $X$ is a solution to $X=AX+B$ then $X = A^*B$. Unfortunately the second part is actually false in general, since $\Sigma^*$ is always a solution when $\epsilon \in A$. For a correct statement, see the Wikipedia page on Arden's rule.
For the first part, all you have to do is substitute $X = A^*B$ and check that both sides are equal. For the second part (once corrected) you have to work a bit more.
You indicate that you are stuck verifying that $A^*B$ is a solution to the equation. I suggest you keep trying – it's not so difficult. Try it with actual regular expressions first.
A: So we know that $A^* = \epsilon + A + A^2 + \cdots $. Are you asking to show how $X = A^* B$ from $X = AX + B$. If so, we can show it simply
\begin{align}
X &= AX + B \\
&= A(AX + B) = A^2 X + AB + B \\
&= A^2 (AX + B) + AB + B = A^3 X + A^2 B + A B + B \\
&\ldots \\
&= B + A B + A^2 B + \cdots \\
&= (\epsilon + A + A^2 + \cdots) B \\
&= A^* B
\end{align}
A: The trick is to write $B$ as $\epsilon B$ and use distributivity:
$$\begin{align*}
A(A^*B)+B&=(AA^*)B+B\\
&=(AA^*)B+\epsilon B\\
&=(AA^*+\epsilon)B\\
&=A^*B
\end{align*}$$
Informally, $A^*B$ stands for any concatenation of $A$-strings, possibly empty, followed by a $B$-string. Putting an $A$ in front forces us to have at least one $A$-string, and to compensate we allow a naked $B$-string as well.
A: You have to be a little bit careful. The statement

If $A$ and $B$ are regular languages, then $A^*B$ is the solution of $X = AX + B$

is actually incorrect, since the equation $X = AX + B$ may have several solutions if the empty word belongs to $A$. The correct statements are

(1) If $A$ does not contain the empty word, then $X=A^*B$ is the unique solution of the equation $X = AX + B$.

and

(2) If $A$ contains the empty word, the solutions of the equation $X = AX + B$
  are the languages of the form $A^*C$ with $B \subseteq C$.

If you prefer a unified version, you could use the following:

(3) The language $A^*B$ is the minimal solution of the equation $X = AX + B$. 

Proof of (3). As Brian Scott explained in his answer, distributivity is the main ingredient to verify that $A^*B$ is a solution of $X = AX + B$. Denoting the empty word by $1$, one gets 
$$
 A(A^*B)+B = A^+B + B = (A^+ + 1)B = A^*B
$$
You can prove that $A^*B$ is the minimal solution as follows. Let $X$ be a solution of the equation $X = AX + B$. Then $B \subseteq X$ and $AX \subseteq X$. Consequently, $A^2X \subseteq AX \subseteq X$ and by induction, $A^nX \subseteq X$ for all $n$. It follows that $A^*X = \sum_{n \geq 0}A^nK \subseteq X$ and finally $A^*B \subseteq A^*X \subseteq X$. 
