debugMinor
Why $P$ cannot have NULL string in Arden's Theorem?
Viewed 0 times
cannotwhyardennulltheoremstringhave
Problem
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?
Solution
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$
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$
Context
StackExchange Computer Science Q#111384, answer score: 2
Revisions (0)
No revisions yet.