# Arden's Lemma in case $X_{i}=AX_{i}$?

Arden's lemma is applied in cases where we have an equation that looks like this: $$X_{i}=AX_{i} + B,$$ with the condition that $\epsilon \notin A$.

But if I have such situation: $$X_{i}=AX_{i},$$ so there's no B, or simply talking we have $B= \varnothing$, thus by the Lemma, we have $$X_{i}=A^{*}\cdot\varnothing$$ which equals to $$X_{i}=\varnothing.$$

Is my reasoning correct?

Your Reasoning is correct. The solution in this case is indeed $X_i = \emptyset$.

• And why is that the case? – Raphael Oct 25 '16 at 12:52

What we have with

$\qquad X = AX + B$

is, quite literally, a recurrence of languages expressed in terms of the symbolic method. $B$ represents the base case of the recurrence. Arden's Lemma just tells you that the smallest fixpoint of this recurrence (read as an inductive definition) is $A^*B$.

Now, if you drop the base case and only have

$\qquad X = AX$,

there are no finite words that can be constructed in this way. Now, the "recurrence" may make sense read as a coinductive definition (that is the solution would be an $X$ containing infinite strings) but not as an inductive one. Hence, the empty set is the only one that solves the equation.