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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ And why is that the case? $\endgroup$
    – Raphael
    Commented Oct 25, 2016 at 12:52
5
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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