Arden's Theorem Proof [closed]

Question

Arden's Theorem: Let $P$ and $Q$ be regular expressions over $\sum$ such that $P$ does not contain the null string. Then, the equation $R = Q + RP$ has a unique solution $R = QP^*$.

Proof: Substitute $R$ by $Q + RP$ in the given equation.
We get $R = Q + (Q + RP) P = Q + QP + RP^2$.
Substitute $R$ again: $ R = Q + QP + (Q+RP)P^2 = Q + QP + QP^2 + RP^3$.

Continuing this substitution we get:
$ R = Q + QP + QP^2 + QP^3 + ... = Q (\epsilon + P+P^2+P^3 + ... ) = QP^*$.

Question: Is this proof correct? I know that the condition that $P$ does not contain $\epsilon$ is needed for the theorem to hold, but I do not see where the proof uses this fact.

Answer 1

There is a problem with the "continuing this substitution" part.

You can't just write dots and assume that's a correct proof: when you write $$R = Q + QP + QP^2 + QP^3 + …$$

the dots can only represent a finite number of powers of $P$ and end with some $RP^{k+1}$, and this is not $QP^*$.

As an example, if $Q = \{a\}$, $P = \{\varepsilon, b\}$, then $R = ab^*+b^*$ is also a solution, and is different than $QP^* = ab^*$. This is because you can't prove that $R\subseteq QP^*$ if $\varepsilon \in P$ (though $QP^*\subseteq R$ even if $\varepsilon \in P$).