3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ And why is that the case? $\endgroup$ – Raphael Oct 25 '16 at 12:52
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.