HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Why $P$ cannot have NULL string in Arden's Theorem?

Submitted by: @import:stackexchange-cs··
0
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$

Context

StackExchange Computer Science Q#111384, answer score: 2

Revisions (0)

No revisions yet.