Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what will be the justification?


Here is the version of Arden's theorem on Wikipedia:

One solution of the language equation $R = Q+RP$ is $R = QP^*$.

If $\epsilon \notin P$, then this is the only solution.

When $\epsilon \in P$, there are more solutions. In fact, we can prove the following result:

The solutions of the language equation $R = Q+RP$, where $\epsilon \in P$, are $R=SP^*$ for all $S \supseteq Q$.

Proof. Let us first show that $SP^*$ is always a solution. Since $\epsilon \in P$, $RP = SP^+ = SP^*$. Since $SP^* \supseteq S \supseteq Q$, $Q + RP = Q + SP^* = SP^* = R$.

Let us now show that all solutions are of this form. Suppose that $R$ is a solution. Clearly $R \supseteq Q$. Since $\epsilon \in P$, this implies that $RP \supseteq R \supseteq Q$, and so $RP = Q + RP = R$. Induction shows that $RP^n = R$ for all $n \in \mathbb{N}$, and so $RP^* = R$. Since $R \supseteq Q$, this is a solution of the required form. $\square$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.